Longest Arithmetic Progression | DP | 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 ; 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 Code
< ? php function lenghtOfLongestAP ( $ set , $ n ) { if ( $ n <= 2 ) return $ n ; $ L [ $ n ] [ $ n ] = array ( array ( ) ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ L [ $ i ] [ $ n - 1 ] = 2 ; for ( $ j = $ n - 2 ; $ j >= 1 ; $ j -- ) { $ 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 ; } $ set1 = array ( 1 , 7 , 10 , 13 , 14 , 19 ) ; $ n1 = sizeof ( $ set1 ) ; echo lenghtOfLongestAP ( $ set1 , $ n1 ) , " " ; $ set2 = array ( 1 , 7 , 10 , 15 , 27 , 29 ) ; $ n2 = sizeof ( $ set2 ) ; echo lenghtOfLongestAP ( $ set2 , $ n2 ) , " " ; $ set3 = array ( 2 , 4 , 6 , 8 , 10 ) ; $ n3 = sizeof ( $ set3 ) ; echo lenghtOfLongestAP ( $ set3 , $ n3 ) , " " ; ? >