Longest Geometric Progression | Returns length of the longest GP subset of set [ ] ; Base cases ; Let us sort the set first ; An entry L [ i ] [ j ] in this table stores LLGP with set [ i ] and set [ 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 set [ j ] by set [ i ] ; Return result ; Driver code
function lenOfLongestGP ( set , n ) { if ( n < 2 ) { return n ; } if ( n == 2 ) { return ( set [ 1 ] % set [ 0 ] == 0 ? 2 : 1 ) ; } set . sort ( function ( a , b ) { return a - b } ) ; let L = new Array ( n ) ; for ( let i = 0 ; i < n ; ++ i ) { L [ i ] = new Array ( n ) ; for ( let j = 0 ; j < n ; ++ j ) { L [ i ] [ j ] = 0 ; } } let llgp = 1 ; for ( let i = 0 ; i < n - 1 ; ++ i ) { if ( set [ n - 1 ] % set [ i ] == 0 ) { L [ i ] [ n - 1 ] = 2 ; if ( 2 > llgp ) llgp = 2 ; } else { L [ i ] [ n - 1 ] = 1 ; } } L [ n - 1 ] [ n - 1 ] = 1 ; for ( let j = n - 2 ; j >= 1 ; -- j ) { let i = j - 1 , k = j + 1 ; while ( i >= 0 && k <= n - 1 ) { if ( set [ i ] * set [ k ] < set [ j ] * set [ j ] ) { ++ k ; } else if ( set [ i ] * set [ k ] > set [ j ] * set [ j ] ) { if ( set [ j ] % set [ i ] == 0 ) { L [ i ] [ j ] = 2 ; if ( 2 > llgp ) llgp = 2 ; } else { L [ i ] [ j ] = 1 ; } -- i ; } else { if ( set [ j ] % set [ i ] == 0 ) { L [ i ] [ j ] = L [ j ] [ k ] + 1 ; if ( L [ i ] [ j ] > llgp ) { llgp = L [ i ] [ j ] ; } } else { L [ i ] [ j ] = 1 ; } -- i ; ++ k ; } } while ( i >= 0 ) { if ( set [ j ] % set [ i ] == 0 ) { L [ i ] [ j ] = 2 ; if ( 2 > llgp ) llgp = 2 ; } else { L [ i ] [ j ] = 1 ; } -- i ; } } return llgp ; } let set1 = [ 1 , 3 , 9 , 27 , 81 , 243 ] ; let n1 = set1 . length ; document . write ( lenOfLongestGP ( set1 , n1 ) + " " ) ; let set2 = [ 1 , 3 , 4 , 9 , 7 , 27 ] ; let n2 = set2 . length ; document . write ( lenOfLongestGP ( set2 , n2 ) + " " ) ; let set3 = [ 2 , 3 , 5 , 7 , 11 , 13 ] ; let n3 = set3 . length ; document . write ( lenOfLongestGP ( set3 , n3 ) + " " ) ;