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
using System ; class GFG { public static int maximizeSum ( int [ ] arr ) { int n = arr . Length ; int sum = 0 ; for ( int i = 0 ; i < n ; i = i + 2 ) sum += arr [ i ] ; int [ ] leftDP = new int [ n / 2 ] ; int [ ] rightDP = new int [ 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 = leftDiff ; } int rightDiff ; if ( i + 1 >= arr . Length ) 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 max = 0 ; for ( int i = 0 ; i < n / 2 ; i ++ ) { max = Math . Max ( max , Math . Max ( leftDP [ i ] , rightDP [ i ] ) ) ; } return max + sum ; } public static void Main ( String [ ] args ) { int [ ] arr = { 7 , 8 , 4 , 5 , 7 , 6 , 8 , 9 , 7 , 3 } ; int ans = maximizeSum ( arr ) ; Console . WriteLine ( ans ) ; } }