**Input**: *A sorted array of numbers.*

**Output**: *The length of the longest arithmetic progression*

**Problem**: *We are given a sorted array and we need to find the length of the longest arithmetic progression.**.*

**Example**:* [1, 9, 10, 11, 16, 21, 28, 30, 31], answer=4.
*

**Complexity**

*:*

*Time O(n^2), Memory 0(n^2)*Before reading this article, it’s strongly recommended to take a look at **this** one, as it describes the basic idea we gonna use in the solution.

The solution will base on a **dynamic programming approach**, as the problem has a property of optimal substructure – we can build arithmetic progression of length N if we already know one with lenght (N-1).

Let’s consider three indices L, M, R, L < M < R, and let’s use the property describing arithmetic sequence mentioned in the **previous article**.** If we know three indices L,M,R that are in a arithmetic progression, and we know that M, R, Q indices are also in the aritmetic progression, then L,M,R,Q are aslo in arithmetic progression**. We will use this property to create **dynamic programming** solution.

Another thing worth considering is that every pair of elements is a arithmetic progression already, what gives us initialization property of an array.

We will have A[L][M] array, where we will store the longest progression length, starting with L, M. We will process the progression from right to left, trying to find L and R for a fixed value of M. The code may look like this:

int longestProgression(vector<int> iProgression) { int A[iProgression.size()][iProgression.size()]; int maxLen = 2; // initialize last columnt values for(int i = 0; i < iProgression.size(); i++) for(int j = 0; j < iProgression.size(); j++) A[i][j] = 2; for(int M = iProgression.size() - 1; M > 0; M--) { int L = M - 1; int R = M + 1; while(L >= 0 && R < iProgression.size()) { int LR = iProgression[L] + iProgression[R]; int M2 = IProgression[M] * 2; if(LR > M2) { L--; } else if(LR < M2) { R++; } else { A[L][M] = A[M][R] + 1; maxLen = max(A[L][M], maxLen); L--; R++; } } } return maxLen; }

The complexity of the solution is O(n^2) and the memory is O(n^2) too.