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+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（intarr[]，intsize）接受输入数组，并返回数组中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