给定一个包含整数元素的数组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+ sum（arr [j]），其中i <j和arr_2 [j] + D = arr_2 [i]
对于更快的方法，在arr_3 [max_size]中添加总和（arr_2 [j]，其中arr [j] + D = arr [i]且j <i）
以整数数组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，取count =大小+1。
计算最大差异diff_max = max_val-min_val和diff_min = min_val-max_val为可能的共同差异。
使用for循环从j = 0到j <size遍历。
设置arr_2 [j] = 1;
对于arr [j]-i> = 1和arr [j]-i <= 1000000设置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