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 ; 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 are 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
def lenghtOfLongestAP ( set , n ) : NEW_LINE INDENT if ( n <= 2 ) : NEW_LINE INDENT return n NEW_LINE DEDENT L = [ [ 0 for x in range ( n ) ] for y in range ( n ) ] NEW_LINE llap = 2 NEW_LINE for i in range ( n ) : NEW_LINE INDENT L [ i ] [ n - 1 ] = 2 NEW_LINE DEDENT for j in range ( n - 2 , 0 , - 1 ) : NEW_LINE INDENT i = j - 1 NEW_LINE k = j + 1 NEW_LINE while ( i >= 0 and k <= n - 1 ) : NEW_LINE INDENT if ( set [ i ] + set [ k ] < 2 * set [ j ] ) : NEW_LINE INDENT k += 1 NEW_LINE DEDENT elif ( set [ i ] + set [ k ] > 2 * set [ j ] ) : NEW_LINE INDENT L [ i ] [ j ] = 2 NEW_LINE i -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT L [ i ] [ j ] = L [ j ] [ k ] + 1 NEW_LINE llap = max ( llap , L [ i ] [ j ] ) NEW_LINE i -= 1 NEW_LINE k += 1 NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT L [ i ] [ j ] = 2 NEW_LINE i -= 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT return llap NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT set1 = [ 1 , 7 , 10 , 13 , 14 , 19 ] NEW_LINE n1 = len ( set1 ) NEW_LINE print ( lenghtOfLongestAP ( set1 , n1 ) ) NEW_LINE set2 = [ 1 , 7 , 10 , 15 , 27 , 29 ] NEW_LINE n2 = len ( set2 ) NEW_LINE print ( lenghtOfLongestAP ( set2 , n2 ) ) NEW_LINE set3 = [ 2 , 4 , 6 , 8 , 10 ] NEW_LINE n3 = len ( set3 ) NEW_LINE print ( lenghtOfLongestAP ( set3 , n3 ) ) NEW_LINE DEDENT