text: Remove an element to maximize the GCD of the given array | C # implementation of the above approach ; Recursive function to return gcd of a and b ; Function to return the maximized gcd after removing a single element from the given array ; Prefix and Suffix arrays ; Single state dynamic programming relation for storing gcd of first i elements from the left in Prefix [ i ] ; Initializing Suffix array ; Single state dynamic programming relation for storing gcd of all the elements having greater than or equal to i in Suffix [ i ] ; If first or last element of the array has to be removed ; If any other element is replaced ; Return the maximized gcd ; Driver code
code: using System ; class GFG { static int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } static int MaxGCD ( int [ ] a , int n ) { int [ ] Prefix = new int [ n + 2 ] ; int [ ] Suffix = new int [ n + 2 ] ; Prefix [ 1 ] = a [ 0 ] ; for ( int i = 2 ; i <= n ; i += 1 ) { Prefix [ i ] = gcd ( Prefix [ i - 1 ] , a [ i - 1 ] ) ; } Suffix [ n ] = a [ n - 1 ] ; for ( int i = n - 1 ; i >= 1 ; i -= 1 ) { Suffix [ i ] = gcd ( Suffix [ i + 1 ] , a [ i - 1 ] ) ; } int ans = Math . Max ( Suffix [ 2 ] , Prefix [ n - 1 ] ) ; for ( int i = 2 ; i < n ; i += 1 ) { ans = Math . Max ( ans , gcd ( Prefix [ i - 1 ] , Suffix [ i + 1 ] ) ) ; } return ans ; } static public void Main ( ) { int [ ] a = { 14 , 17 , 28 , 70 } ; int n = a . Length ; Console . Write ( MaxGCD ( a , n ) ) ; } }