Longest Arithmetic Progression - Dynamic Programming Solutions

This is a C++ Program that Solves Length of Longest Arithmetic Progression Problem using Dynamic Programming technique.

Problem Description

Given sorted array of integers, find the Length of the Longest Arithmetic Progression (LLAP) in it.

Problem Solution

If elements a,b,c,d,e are in AP, then b=(a+c), c=(b+d), d=(c+e). Also, c=(a+e). We will be using this observation to find out the answer. We will create a matrix dp to memoize values where dp[i][j]=length of the longest AP with first element a[i] and second element a[j]. We will iterate over all elements considering it as second element of the AP and find out the longest possible length of AP with it and store it in the matrix.

Expected Input and Output

Case-1:

array[]=2 4 5 7 8 10 11 12
llap=4

Program/Source Code for Brute force solution

```
//brute force
```
```
#include<bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
 
```
```
int llap(int n, vector<int> &a)
```
```
{
```
```
    if(n<=2)
```
```
        return n;
```
```
 
```
```
    int i,j,k,d;
```
```
    int mxl=2;
```
```
    int current;
```
```
    int last;
```
```
 
```

    //i will be the index of first element of the ap

```
    for(i=0;i<(n-mxl);i++)
```
```
    {
```

        //j will be the index of second element of the ap

```
        for(j=i+1;j<(n-mxl+1);j++)
```
```
        {
```
```
            //common difference
```
```
            d=a[j]-a[i];
```
```
            last=a[j];
```
```
            current=2;
```
```
 
```
```
            for(k=j+1;k<n;k++)
```
```
            {
```
```
                if(a[k]-last==d)
```
```
                {
```

                    //here is our element

```
                    current++;
```
```
                    last=a[k];
```
```
 
```
```
                }
```
```
            }
```
```
 
```
```
            mxl=max(mxl,current);
```
```
 
```
```
        }
```
```
 
```
```
    }
```
```
 
```
```
    return mxl;
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int n;
```
```
    int i,j;
```
```
 
```

    cout<<"Enter the number of elements in the array  ";

```
    cin>>n;
```
```
 
```
```
    vector<int> a(n);
```
```
 
```
```
    for(i=0;i<n;i++)
```
```
    {
```
```
        cin>>a[i];
```
```
    }
```
```
 
```

    cout<<"The length of the longest arithmetic progression in the given sorted sequence is ";

```
    cout<<llap(n,a);
```
```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program/Source Code for DP solution

Here is source code of the C++ Program to Solve Length of Longest Arithmetic Progression Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
//DP
```
```
#include<bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
 
```
```
int llap(int n, vector<int> &a)
```
```
{
```
```
    if(n<=2)
```
```
        return n;
```
```
 
```
```
    int i,j,k;
```
```
    int mxl=2;
```
```
 
```

    vector<vector<int> > dp(n,vector<int>(n));

    //dp[i][j]=length of the longest AP with first element a[i] and second element a[j]

```
 
```
```
    //initialization
```

    //if second term is the last term of array, length is always 2

```
    for(i=0;i<n;i++)
```
```
        dp[i][n-1]=2;
```
```
 
```
```
    //j is the second element of the AP
```
```
    for(j=n-2;j>=1;j--)
```
```
    {
```

        //i is the first element of the AP

```
        i=j-1;
```
```
        k=j+1;
```
```
 
```
```
        while(i>=0 && k<n)
```
```
        {
```
```
            if(a[i]+a[k]==2*a[j])
```
```
            {
```
```
                //i, j, k are in AP
```
```
                dp[i][j]=dp[j][k]+1;
```
```
 
```
```
                if(mxl<dp[i][j])
```
```
                    mxl=dp[i][j];
```
```
 
```
```
                i--;
```
```
                k++;
```
```
            }
```
```
 
```
```
            else if(a[i]+a[k]<2*a[j])
```
```
            {
```
```
                k++;
```
```
            }
```
```
 
```
```
            else
```
```
            {
```
```
                dp[i][j]=2;
```
```
                i--;
```
```
            }
```
```
        }
```
```
 
```

        //initialize every remaining value of i for this j

```
        while(i>=0)
```
```
        {
```
```
            dp[i][j]=2;
```
```
            i--;
```
```
        }
```
```
 
```
```
 
```
```
    }
```
```
 
```
```
 
```
```
    return mxl;
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int n;
```
```
    int i;
```
```
 
```

    cout<<"Enter the number of elements in the array  ";

```
    cin>>n;
```
```
 
```
```
    vector<int> a(n);
```
```
 
```
```
    for(i=0;i<n;i++)
```
```
    {
```
```
        cin>>a[i];
```
```
    }
```
```
 
```

    cout<<"The length of the longest arithmetic progression in the given sorted sequence is ";

```
    cout<<llap(n,a);
```
```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, the user input the elements in the array. The values are passed as parameters to the function llap. The function llap returns the length of the longest arithemtic progression which is displayed.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Runtime Test Cases

 
Case-1:
$ g++ llap.cpp
$ ./a.out
Enter the number of elements in the array  8
2 4 5 7 8 10 11 12
The length of the longest arithmetic progression in the given sorted sequence is 4

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

« Prev - Stock Market Problem using Dynamic Programming

» Next - Make Palindrome Problem – Dynamic Programming Solutions

Related Posts:

Check Data Structure Books
Practice Design & Analysis of Algorithms MCQ
Apply for Computer Science Internship
Check Programming Books
Practice Computer Science MCQs

Recommended Articles: