**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.

### Like this:

Like Loading...

*Related*

Implementation is incorrect.

if(LR > M2)

{

A[L][M] = 2;

}

—>

if(LR > M2)

{

L–; /* Without this in some inputs the code will run into infinite loop */

A[L][M] = 2; /* You can keep this, or remove it as A[L][M] is already initialized to 2 */

}

Thanks! Obviously you are right. I think I just missed it while writting the code.

Hi Buddy, sorry I’m a noob and cannot understand how the [n][n] table works. Can you please explain this step

else

{

A[L][M] = A[M][R] + 1;

maxLen = max(A[L][M], maxLen);

L–; R++;

}

Also if all the steps of the progression need to be saved, what code is to be added?