Longest Arithmetic Progression

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.