Longest Arithmetic Progression | DP | C ++ program to find Length of the Longest AP ( llap ) in a given sorted set . The code strictly implements the algorithm provided in the reference . ; Returns length of the longest AP subset in a given set ; Create a table and initialize all values as 2. The value of L [ i ] [ j ] stores LLAP with set [ i ] and set [ j ] as first two elements of AP . Only valid entries are the entries where j > i ; Initialize the result ; Fill entries in last column as 2. There will always be two elements in AP with last number of set as second element in AP ; Consider every element as second element of AP ; Search for i and k for j ; Before changing i , set L [ i ] [ j ] as 2 ; Found i and k for j , LLAP with i and j as first two elements is equal to LLAP with j and k as first two elements plus 1. L [ j ] [ k ] must have been filled before as we run the loop from right side ; Update overall LLAP , if needed ; Change i and k to fill more L [ i ] [ j ] values for current j ; If the loop was stopped due to k becoming more than n - 1 , set the remaining entities in column j as 2 ; Driver program to test above function
#include <iostream> NEW_LINE using namespace std ; int lenghtOfLongestAP ( int set [ ] , int n ) { if ( n <= 2 ) return n ; int L [ n ] [ n ] ; int llap = 2 ; for ( int i = 0 ; i < n ; i ++ ) L [ i ] [ n - 1 ] = 2 ; for ( int j = n - 2 ; j >= 1 ; j -- ) { int i = j - 1 , k = j + 1 ; while ( i >= 0 && k <= n - 1 ) { if ( set [ i ] + set [ k ] < 2 * set [ j ] ) k ++ ; else if ( set [ i ] + set [ k ] > 2 * set [ j ] ) { L [ i ] [ j ] = 2 , i -- ; } else { L [ i ] [ j ] = L [ j ] [ k ] + 1 ; llap = max ( llap , L [ i ] [ j ] ) ; i -- ; k ++ ; } } while ( i >= 0 ) { L [ i ] [ j ] = 2 ; i -- ; } } return llap ; } int main ( ) { int set1 [ ] = { 1 , 7 , 10 , 13 , 14 , 19 } ; int n1 = sizeof ( set1 ) / sizeof ( set1 [ 0 ] ) ; cout << lenghtOfLongestAP ( set1 , n1 ) << endl ; int set2 [ ] = { 1 , 7 , 10 , 15 , 27 , 29 } ; int n2 = sizeof ( set2 ) / sizeof ( set2 [ 0 ] ) ; cout << lenghtOfLongestAP ( set2 , n2 ) << endl ; int set3 [ ] = { 2 , 4 , 6 , 8 , 10 } ; int n3 = sizeof ( set3 ) / sizeof ( set3 [ 0 ] ) ; cout << lenghtOfLongestAP ( set3 , n3 ) << endl ; return 0 ; }