Maximize sum of remaining elements after every removal of the array half with greater sum | Function to find the maximum sum ; Base case len of array is 1 ; Stores the final result ; Traverse the array ; Store left prefix sum ; Store right prefix sum ; Compare the left and right ; If both are equal apply the optimal method ; Update with minimum ; Return the final ans ; Function to print maximum sum ; Dicitionary to store prefix sums ; Traversing the array ; Add prefix sum of the array ; Driver Code ; Function call
function maxweight ( s , e , pre ) { if ( s == e ) return 0 ; let ans = 0 ; for ( let i = s ; i < e ; i ++ ) { if ( ! pre [ i ] ) pre [ i ] = 0 ; if ( ! pre [ e ] ) pre [ e ] = 0 ; if ( ! pre [ s - 1 ] ) pre [ s - 1 ] = 0 ; let left = pre [ i ] - pre [ s - 1 ] ; let right = pre [ e ] - pre [ i ] ; if ( left < right ) ans = Math . max ( ans , left + maxweight ( s , i , pre ) ) ; if ( left == right ) { ans = Math . max ( ans , Math . max ( left + maxweight ( s , i , pre ) , right + maxweight ( i + 1 , e , pre ) ) ) ; } if ( left > right ) ans = Math . max ( ans , right + maxweight ( i + 1 , e , pre ) ) ; } return ans ; } function maxSum ( arr ) { let pre = new Map ; pre [ - 1 ] = 0 ; pre [ 0 ] = arr [ 0 ] ; for ( let i = 1 ; i < arr . length ; i ++ ) { pre [ i ] = pre [ i - 1 ] + arr [ i ] ; } document . write ( maxweight ( 0 , arr . length - 1 , pre ) ) ; } arr = [ 6 , 2 , 3 , 4 , 5 , 5 ] ; maxSum ( arr ) ;