Remove an element to maximize the GCD of the given array | Python3 implementation of the above approach ; 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
import math as mt NEW_LINE def MaxGCD ( a , n ) : NEW_LINE INDENT Prefix = [ 0 for i in range ( n + 2 ) ] NEW_LINE Suffix = [ 0 for i in range ( n + 2 ) ] NEW_LINE Prefix [ 1 ] = a [ 0 ] NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT Prefix [ i ] = mt . gcd ( Prefix [ i - 1 ] , a [ i - 1 ] ) NEW_LINE DEDENT Suffix [ n ] = a [ n - 1 ] NEW_LINE for i in range ( n - 1 , 0 , - 1 ) : NEW_LINE INDENT Suffix [ i ] = mt . gcd ( Suffix [ i + 1 ] , a [ i - 1 ] ) NEW_LINE DEDENT ans = max ( Suffix [ 2 ] , Prefix [ n - 1 ] ) NEW_LINE for i in range ( 2 , n ) : NEW_LINE INDENT ans = max ( ans , mt . gcd ( Prefix [ i - 1 ] , Suffix [ i + 1 ] ) ) NEW_LINE DEDENT return ans NEW_LINE DEDENT a = [ 14 , 17 , 28 , 70 ] NEW_LINE n = len ( a ) NEW_LINE print ( MaxGCD ( a , n ) ) NEW_LINE