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