Reverse a subarray to maximize sum of even | Function to return maximized sum at even indices ; Stores difference with element on the left ; Stores difference with element on the right ; Compute and store left difference ; For first index ; If previous difference is positive ; Otherwise ; For the last index ; Otherwise ; For first index ; If the previous difference is positive ; Driver Code
def maximizeSum ( arr ) : NEW_LINE INDENT n = len ( arr ) NEW_LINE sum = 0 NEW_LINE for i in range ( 0 , n , 2 ) : NEW_LINE INDENT sum += arr [ i ] NEW_LINE DEDENT leftDP = [ 0 ] * ( n ) NEW_LINE rightDP = [ 0 ] * ( n ) NEW_LINE c = 0 NEW_LINE for i in range ( 1 , n , 2 ) : NEW_LINE INDENT leftDiff = arr [ i ] - arr [ i - 1 ] NEW_LINE if ( c - 1 < 0 ) : NEW_LINE INDENT leftDP [ i ] = leftDiff NEW_LINE DEDENT else : NEW_LINE INDENT if ( leftDP [ i ] > 0 ) : NEW_LINE INDENT leftDP [ i ] = ( leftDiff + leftDP [ i - 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT leftDP [ i ] = leftDiff NEW_LINE DEDENT DEDENT rightDiff = 0 NEW_LINE if ( i + 1 >= len ( arr ) ) : NEW_LINE INDENT rightDiff = 0 NEW_LINE DEDENT else : NEW_LINE INDENT rightDiff = arr [ i ] - arr [ i + 1 ] NEW_LINE DEDENT if ( c - 1 < 0 ) : NEW_LINE INDENT rightDP [ i ] = rightDiff NEW_LINE DEDENT else : NEW_LINE INDENT if ( rightDP [ i ] > 0 ) : NEW_LINE INDENT rightDP [ i ] = ( rightDiff + rightDP [ i - 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT rightDP [ i ] = rightDiff NEW_LINE DEDENT DEDENT c += 1 NEW_LINE DEDENT maxm = 0 NEW_LINE for i in range ( n // 2 ) : NEW_LINE INDENT maxm = max ( maxm , max ( leftDP [ i ] , rightDP [ i ] ) ) NEW_LINE DEDENT return maxm + sum NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 7 , 8 , 4 , 5 , 7 , 6 , 8 , 9 , 7 , 3 ] NEW_LINE ans = maximizeSum ( arr ) NEW_LINE print ( ans ) NEW_LINE DEDENT