Reverse a subarray to maximize sum of even | C ++ program to implement the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximizeSum ( int arr [ ] , int n ) { int sum = 0 ; for ( int i = 0 ; i < n ; i = i + 2 ) sum += arr [ i ] ; int leftDP [ n / 2 ] ; int rightDP [ n / 2 ] ; int c = 0 ; for ( int i = 1 ; i < n ; i = i + 2 ) { int leftDiff = arr [ i ] - arr [ i - 1 ] ; if ( c - 1 < 0 ) leftDP = leftDiff ; else { if ( leftDP > 0 ) leftDP = leftDiff + leftDP ; else leftDP [ i ] = leftDiff ; } int rightDiff ; if ( i + 1 >= n ) rightDiff = 0 ; else rightDiff = arr [ i ] - arr [ i + 1 ] ; if ( c - 1 < 0 ) rightDP = rightDiff ; else { if ( rightDP > 0 ) rightDP = rightDiff + rightDP ; else rightDP = rightDiff ; } c ++ ; } int maxi = 0 ; for ( int i = 0 ; i < n / 2 ; i ++ ) { maxi = max ( maxi , max ( leftDP [ i ] , rightDP [ i ] ) ) ; } return maxi + sum ; } int main ( ) { int arr [ ] = { 7 , 8 , 4 , 5 , 7 , 6 , 8 , 9 , 7 , 3 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int ans = maximizeSum ( arr , n ) ; cout << ( ans ) ; }