C ++の配列内のAP（等差数列）サブシーケンスの数

整数要素を含む配列arr[]が与えられます。目標は、arr[]内の等差数列サブシーケンスの数をカウントすることです。 arr[]内の要素の範囲は[1,1000000]です。

空のシーケンスまたは単一の要素もカウントされます。

例を挙げて理解しましょう。

例

入力- arr [] ={1,2,3}

出力- 配列内のAP（等差数列）サブシーケンスの数は次のとおりです。8

説明- 次のサブシーケンスがAPを形成します：-

{}、{1}、{2}、{3}、{1,2}、{2,3}、{1,3}、{1,2,3}

入力- arr [] ={2,4,5,8}

出力- 配列内のAP（等差数列）サブシーケンスの数は次のとおりです。12

説明- 次のサブシーケンスがAPを形成します：-

{}、{2}、{4}、{5}、{8}、{2,4}、{2,5}、{2,8}、{4,5}、{4,8}、{ 5,8}、{2,5,8}

以下のプログラムで使用されているアプローチは次のとおりです

• 空のシーケンスもAPです。
• 単一の値はAPでもあります。
• 配列内の最小値と最大値をmax_valおよびmin_valとして検索します。すべてのAPサブシーケンスに共通する違いは、[min_val --max_val、max_val --min_val]
の間です。
• ここで、一般的な違いごとに、動的計画法を使用してサブシーケンスを見つけ、arr_2[size]に格納します。
• 長さ2または2を超えるサブシーケンスは、arr_2 [i] -1の合計にはなりません。ここで、iは[0,2]で、差はDです。
• arr_2 [i] =1+合計（arr [j]）ここで、i
• より高速なアプローチのために、arr_3 [max_size]に合計（arr_2[j]とarr[j] + D =arr[i]およびj
• 整数配列arr[]を入力として受け取ります。
• 関数AP_subsequence（int arr []、int size）は入力配列を受け取り、配列内のAP（等差数列）サブシーケンスの数を返します。
• 初期カウントを0とします。
• サブシーケンスカウントを格納するための変数max_val、min_val、arr_2 [size]と、合計を格納するためのarr_3[max_size]を取得します。
• forループを使用してarr[]をトラバースし、最大要素と最小要素を見つけて、max_valとmin_valに格納します。
• 単一要素APと空のAPの場合はカウント=サイズ+1を取ります。
• 可能な限り一般的な差異として、最大差異diff_max=max_val-min_valおよびdiff_min=min_val--max_valを計算します。
• forループを使用してj=0からj
• arr_2 [j]=1に設定します;
• arr [j] --i>=1およびarr[j]--i <=1000000 set arr_2 [j] + =arr_3 [arr[j]--i]の場合。
• カウントするためにarr_2[j]-1を追加します。
• 合計をarr_3[arr[j]] =arr_3 [arr [j]] +arr_2[j]として更新します。
• 最後に結果としてカウントを返します。

例

#include<bits/stdc++.h>

using namespace std;
#define max_size 10000

int AP_subsequence(int arr[], int size) {
   int count = 0;
   int max_val = INT_MAX;
   int min_val = INT_MIN;
   int arr_2[size];
   int arr_3[max_size];

   for (int i = 0; i < size; i++) {
      max_val = min(max_val, arr[i]);
      min_val = max(min_val, arr[i]);
   }
   count = size + 1;
   int diff_max = max_val - min_val;
   int diff_min = min_val - max_val;
   for (int i = diff_max; i <= diff_min; i++) {
      memset(arr_3, 0, sizeof arr_3);
      for (int j = 0; j < size; j++) {
         arr_2[j] = 1;
         if (arr[j] - i >= 1) {
            if (arr[j] - i <= 1000000) {
               arr_2[j] += arr_3[arr[j] - i];
            }
         }
         count += arr_2[j] - 1;
         arr_3[arr[j]] = arr_3[arr[j]] + arr_2[j];
      }
   }
   return count;
}
int main() {
   int arr[] = {1,1,6,7,8};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout << "Count of AP (Arithmetic Progression) Subsequences in an array are: " << AP_subsequence(arr, size);
   return 0;
}

上記のコードを実行すると、次の出力が生成されます-

出力

Count of AP (Arithmetic Progression) Subsequences in an array are: 17