Maximum Subarray Sum possible by replacing an Array element by its Square | Function to find the maximum subarray sum possible ; Stores sum without squaring ; Stores sum squaring ; Stores the maximum subarray sum ; Either extend the subarray or start a new subarray ; Either extend previous squared subarray or start a new subarray by squaring the current element ; Update maximum subarray sum ; Return answer ; Driver Code ; Function call
def getMaxSum ( a , n ) : NEW_LINE INDENT dp = [ [ 0 for x in range ( 2 ) ] for y in range ( n ) ] NEW_LINE dp [ 0 ] [ 0 ] = a [ 0 ] NEW_LINE dp [ 0 ] [ 1 ] = a [ 0 ] * a [ 0 ] NEW_LINE max_sum = max ( dp [ 0 ] [ 0 ] , dp [ 0 ] [ 1 ] ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT dp [ i ] [ 0 ] = max ( a [ i ] , dp [ i - 1 ] [ 0 ] + a [ i ] ) NEW_LINE dp [ i ] [ 1 ] = max ( dp [ i - 1 ] [ 1 ] + a [ i ] , a [ i ] * a [ i ] ) NEW_LINE dp [ i ] [ 1 ] = max ( dp [ i ] [ 1 ] , dp [ i - 1 ] [ 0 ] + a [ i ] * a [ i ] ) NEW_LINE max_sum = max ( max_sum , dp [ i ] [ 1 ] ) NEW_LINE max_sum = max ( max_sum , dp [ i ] [ 0 ] ) NEW_LINE DEDENT return max_sum NEW_LINE DEDENT n = 5 NEW_LINE a = [ 1 , - 5 , 8 , 12 , - 8 ] NEW_LINE print ( getMaxSum ( a , n ) ) NEW_LINE