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
using System ; class GFG { static int lenOfLongestGP ( int [ ] Set , int n ) { if ( n < 2 ) { return n ; } if ( n == 2 ) { return ( Set [ 1 ] % Set [ 0 ] == 0 ? 2 : 1 ) ; } Array . Sort ( Set ) ; int [ , ] L = new int [ 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 ; 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 ; } public static void Main ( String [ ] args ) { int [ ] set1 = { 1 , 3 , 9 , 27 , 81 , 243 } ; int n1 = set1 . Length ; Console . Write ( lenOfLongestGP ( set1 , n1 ) + " STRNEWLINE " ) ; int [ ] set2 = { 1 , 3 , 4 , 9 , 7 , 27 } ; int n2 = set2 . Length ; Console . Write ( lenOfLongestGP ( set2 , n2 ) + " STRNEWLINE " ) ; int [ ] set3 = { 2 , 3 , 5 , 7 , 11 , 13 } ; int n3 = set3 . Length ; Console . Write ( lenOfLongestGP ( set3 , n3 ) + " STRNEWLINE " ) ; } }