Get this book -> Problems on Array: For Interviews and Competitive Programming

Reading time: 20 minutes | coding time: 10 minutes

Given an array of **n** positive integers. The task is to count the number of Arithmetic Progression subsequence in the array.

Arithmetic Progression is defined as a series of **a, a + d, a + 2 * d,** etc.

By difference of Arithmetic Progression we mean d.

**Let us look at few of Examples:-**

```
Input : arr[] = { 1, 2, 3 }
Output : 8
Arithmetic Progression subsequence from the
given array are: {}, { 1 }, { 2 }, { 3 }, { 1, 2 },
{ 2, 3 }, { 1, 3 }, { 1, 2, 3 }.
Input : arr[] = { 10, 20, 30, 45 }
Output : 12
Input : arr[] = { 1, 2, 3, 4, 5 }
Output : 23
```

**Note**: 1.Empty sequence or single element sequence is Arithmetic Progression.

2.we have considered A[i] in range 1 to 1000000(inclusive).

Since empty sequence and single element sequence is also arithmetic progression, so we **initialize** the **answer** with **n(number of element in the array) + 1**.

Now, we need to find the arithmetic progression subsequence of length **greater than or equal to 2**. Let minimum and maximum of the array be **minarr** and **maxarr** respectively. Observe, in all the arithmetic progression subsequences, the range of common difference will be from (**minarr â€“ maxarr) to (maxarr â€“ minarr)**.

We will solve this problem by **dynamic programming**. Let **dp[i]** denote the number of **AP's ending at i** and having difference equal to **d**. So if our current number is equal to A[i], we need to find all the positions **j < i** such that **A[j] = A[i] - diff** and we will take **sum of dp[j]** for those **j**'s. It is equivalent to extending the APs ending at position j with the element at position i.

```
Hence dp[i] = sum_(j = 1 to i - 1) dp[j] such that A[j] = A[i] - diff
```

we can **optimize** this by maintaining a sum array where **sum[x]** will record sum of all the dp's where the value of array elements was **x**.

```
sum[x] = sum of all dp[i]'s such that A[i] = x.
```

After this, our dp will be.

```
Hence dp[i] = sum[A[i] - diff] + 1.
```

Now with this optimization, our dp computation will take O(N) time.

### Complexity

Time complexity: O(n)

### Implementation

Let us look at Dynamic programming approach:-

### C

```
#include<bits/stdc++.h>
#define MAX 1000001
using namespace std;
int numofAP(int a[], int n)
{
// initializing the minimum value and
// maximum value of the array.
int minarr = INT_MAX, maxarr = INT_MIN;
// Finding the minimum and maximum
// value of the array.
for (int i = 0; i < n; i++)
{
minarr = min(minarr, a[i]);
maxarr = max(maxarr, a[i]);
}
// dp[i] is going to store count of APs ending
// with arr[i].
// sum[j] is going to store sun of all dp[]'s
// with j as an AP element.
int dp[n], sum[MAX];
// Initialize answer with n + 1 as single elements
// and empty array are also DP.
int ans = n + 1;
// Traversing with all common difference.
for (int d=(minarr-maxarr); d<=(maxarr-minarr); d++)
{
memset(sum, 0, sizeof sum);
// Traversing all the element of the array.
for (int i = 0; i < n; i++)
{
// Initialize dp[i] = 1.
dp[i] = 1;
// Adding counts of APs with given differences
// and a[i] is last element.
// We consider all APs where an array element
// is previous element of AP with a particular
// difference
if (a[i] - d >= 1 && a[i] - d <= 1000000)
dp[i] += sum[a[i] - d];
ans += dp[i] - 1;
sum[a[i]] += dp[i];
}
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3 };
int n = sizeof(arr)/sizeof(arr[0]);
cout << numofAP(arr, n) << endl;
return 0;
}
```

**Output:**

8