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
  1. //brute force
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5.  
  6. int llap(int n, vector<int> &a)
  7. {
  8.     if(n<=2)
  9.         return n;
  10.  
  11.     int i,j,k,d;
  12.     int mxl=2;
  13.     int current;
  14.     int last;
  15.  
  16.     //i will be the index of first element of the ap
  17.     for(i=0;i<(n-mxl);i++)
  18.     {
  19.         //j will be the index of second element of the ap
  20.         for(j=i+1;j<(n-mxl+1);j++)
  21.         {
  22.             //common difference
  23.             d=a[j]-a[i];
  24.             last=a[j];
  25.             current=2;
  26.  
  27.             for(k=j+1;k<n;k++)
  28.             {
  29.                 if(a[k]-last==d)
  30.                 {
  31.                     //here is our element
  32.                     current++;
  33.                     last=a[k];
  34.  
  35.                 }
  36.             }
  37.  
  38.             mxl=max(mxl,current);
  39.  
  40.         }
  41.  
  42.     }
  43.  
  44.     return mxl;
  45. }
  46.  
  47. int main()
  48. {
  49.     int n;
  50.     int i,j;
  51.  
  52.     cout<<"Enter the number of elements in the array  ";
  53.     cin>>n;
  54.  
  55.     vector<int> a(n);
  56.  
  57.     for(i=0;i<n;i++)
  58.     {
  59.         cin>>a[i];
  60.     }
  61.  
  62.     cout<<"The length of the longest arithmetic progression in the given sorted sequence is ";
  63.     cout<<llap(n,a);
  64.  
  65.     cout<<endl;
  66.     return 0;
  67. }
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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
  1. //DP
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5.  
  6. int llap(int n, vector<int> &a)
  7. {
  8.     if(n<=2)
  9.         return n;
  10.  
  11.     int i,j,k;
  12.     int mxl=2;
  13.  
  14.     vector<vector<int> > dp(n,vector<int>(n));
  15.     //dp[i][j]=length of the longest AP with first element a[i] and second element a[j]
  16.  
  17.     //initialization
  18.     //if second term is the last term of array, length is always 2 
  19.     for(i=0;i<n;i++)
  20.         dp[i][n-1]=2;
  21.  
  22.     //j is the second element of the AP
  23.     for(j=n-2;j>=1;j--)
  24.     {
  25.         //i is the first element of the AP
  26.         i=j-1;
  27.         k=j+1;
  28.  
  29.         while(i>=0 && k<n)
  30.         {
  31.             if(a[i]+a[k]==2*a[j])
  32.             {
  33.                 //i, j, k are in AP
  34.                 dp[i][j]=dp[j][k]+1;
  35.  
  36.                 if(mxl<dp[i][j])
  37.                     mxl=dp[i][j];
  38.  
  39.                 i--;
  40.                 k++;
  41.             }
  42.  
  43.             else if(a[i]+a[k]<2*a[j])
  44.             {
  45.                 k++;
  46.             }
  47.  
  48.             else
  49.             {
  50.                 dp[i][j]=2;
  51.                 i--;
  52.             }
  53.         }
  54.  
  55.         //initialize every remaining value of i for this j
  56.         while(i>=0)
  57.         {
  58.             dp[i][j]=2;
  59.             i--;
  60.         }
  61.  
  62.  
  63.     }
  64.  
  65.  
  66.     return mxl;
  67. }
  68.  
  69. int main()
  70. {
  71.     int n;
  72.     int i;
  73.  
  74.     cout<<"Enter the number of elements in the array  ";
  75.     cin>>n;
  76.  
  77.     vector<int> a(n);
  78.  
  79.     for(i=0;i<n;i++)
  80.     {
  81.         cin>>a[i];
  82.     }
  83.  
  84.     cout<<"The length of the longest arithmetic progression in the given sorted sequence is ";
  85.     cout<<llap(n,a);
  86.  
  87.     cout<<endl;
  88.     return 0;
  89. }
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.

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.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.