Longest Geometric Progression | Returns length of the longest GP subset of sett [ ] ; Base cases ; let us sort the sett first ; An entry L [ i ] [ j ] in this table stores LLGP with sett [ i ] and sett [ j ] as first two elements of GP and j > i . ; Initialize result ( A single element is always a GP ) ; Initialize values of last column ; Consider every element as second element of GP ; Search for i and k for j ; Two cases when i , j and k don 't form  a GP. ; i , j and k form GP , LLGP with i and j as first two elements is equal to LLGP 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 LLGP ; 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 entries in column j as 1 or 2 based on divisibility of sett [ j ] by sett [ i ] ; Return result ; Driver code
def lenOfLongestGP ( sett , n ) : NEW_LINE INDENT if n < 2 : NEW_LINE INDENT return n NEW_LINE DEDENT if n == 2 : NEW_LINE INDENT return 2 if ( sett [ 1 ] % sett [ 0 ] == 0 ) else 1 NEW_LINE DEDENT sett . sort ( ) NEW_LINE L = [ [ 0 for i in range ( n ) ] for i in range ( n ) ] NEW_LINE llgp = 1 NEW_LINE for i in range ( 0 , n - 1 ) : NEW_LINE INDENT if sett [ n - 1 ] % sett [ i ] == 0 : NEW_LINE INDENT L [ i ] [ n - 1 ] = 2 NEW_LINE if 2 > llgp : NEW_LINE INDENT llgp = 2 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT L [ i ] [ n - 1 ] = 1 NEW_LINE DEDENT DEDENT L [ n - 1 ] [ n - 1 ] = 1 NEW_LINE 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 sett [ i ] * sett [ k ] < sett [ j ] * sett [ j ] : NEW_LINE INDENT k += 1 NEW_LINE DEDENT elif sett [ i ] * sett [ k ] > sett [ j ] * sett [ j ] : NEW_LINE INDENT if sett [ j ] % sett [ i ] == 0 : NEW_LINE INDENT L [ i ] [ j ] = 2 NEW_LINE DEDENT else : NEW_LINE INDENT L [ i ] [ j ] = 1 NEW_LINE DEDENT i -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT if sett [ j ] % sett [ i ] == 0 : NEW_LINE INDENT L [ i ] [ j ] = L [ j ] [ k ] + 1 NEW_LINE if L [ i ] [ j ] > llgp : NEW_LINE INDENT llgp = L [ i ] [ j ] NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT L [ i ] [ j ] = 1 NEW_LINE DEDENT i -= 1 NEW_LINE k += 1 NEW_LINE DEDENT DEDENT while i >= 0 : NEW_LINE INDENT if sett [ j ] % sett [ i ] == 0 : NEW_LINE INDENT L [ i ] [ j ] = 2 NEW_LINE DEDENT else : NEW_LINE INDENT L [ i ] [ j ] = 1 NEW_LINE DEDENT i -= 1 NEW_LINE DEDENT DEDENT return llgp NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT set1 = [ 1 , 3 , 9 , 27 , 81 , 243 ] NEW_LINE n1 = len ( set1 ) NEW_LINE print ( lenOfLongestGP ( set1 , n1 ) ) NEW_LINE set2 = [ 1 , 3 , 4 , 9 , 7 , 27 ] NEW_LINE n2 = len ( set2 ) NEW_LINE print ( lenOfLongestGP ( set2 , n2 ) ) NEW_LINE set3 = [ 2 , 3 , 5 , 7 , 11 , 13 ] NEW_LINE n3 = len ( set3 ) NEW_LINE print ( lenOfLongestGP ( set3 , n3 ) ) NEW_LINE DEDENT