Longest Geometric Progression | C ++ program to find length of the longest geometric progression in a given set ; 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
#include <iostream> NEW_LINE #include <algorithm> NEW_LINE using namespace std ; int lenOfLongestGP ( int set [ ] , int n ) { if ( n < 2 ) return n ; if ( n == 2 ) return ( set [ 1 ] % set [ 0 ] == 0 ) ? 2 : 1 ; sort ( set , set + n ) ; int L [ n ] [ n ] ; int llgp = 1 ; for ( int 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 ( 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 ] < 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 ; } 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 ; } int main ( ) { int set1 [ ] = { 1 , 3 , 9 , 27 , 81 , 243 } ; int n1 = sizeof ( set1 ) / sizeof ( set1 [ 0 ] ) ; cout << lenOfLongestGP ( set1 , n1 ) << " STRNEWLINE " ; int set2 [ ] = { 1 , 3 , 4 , 9 , 7 , 27 } ; int n2 = sizeof ( set2 ) / sizeof ( set2 [ 0 ] ) ; cout << lenOfLongestGP ( set2 , n2 ) << " STRNEWLINE " ; int set3 [ ] = { 2 , 3 , 5 , 7 , 11 , 13 } ; int n3 = sizeof ( set3 ) / sizeof ( set3 [ 0 ] ) ; cout << lenOfLongestGP ( set3 , n3 ) << " STRNEWLINE " ; return 0 ; }