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
function maximizeSum ( arr ) { let n = arr . length ; let sum = 0 ; for ( let i = 0 ; i < n ; i = i + 2 ) sum += arr [ i ] ; let leftDP = new Array ( Math . floor ( n / 2 ) ) ; let rightDP = new Array ( Math . floor ( n / 2 ) ) ; for ( let i = 0 ; i < n / 2 ; i ++ ) { leftDP [ i ] = 0 ; rightDP [ i ] = 0 ; } let c = 0 ; for ( let i = 1 ; i < n ; i = i + 2 ) { let leftDiff = arr [ i ] - arr [ i - 1 ] ; if ( c - 1 < 0 ) leftDP [ i ] = leftDiff ; else { if ( leftDP [ i ] > 0 ) leftDP [ i ] = leftDiff + leftDP [ i - 1 ] ; else leftDP [ i ] = leftDiff ; } let rightDiff ; if ( i + 1 >= arr . length ) rightDiff = 0 ; else rightDiff = arr [ i ] - arr [ i + 1 ] ; if ( c - 1 < 0 ) rightDP [ i ] = rightDiff ; else { if ( rightDP [ i ] > 0 ) rightDP [ i ] = rightDiff + rightDP [ i - 1 ] ; else rightDP [ i ] = rightDiff ; } c ++ ; } let max = 0 ; for ( let i = 0 ; i < n / 2 ; i ++ ) { max = Math . max ( max , Math . max ( leftDP [ i ] , rightDP [ i ] ) ) ; } return max + sum ; } let arr = [ 7 , 8 , 4 , 5 , 7 , 6 , 8 , 9 , 7 , 3 ] ; let ans = maximizeSum ( arr ) ; document . write ( ans ) ;