Maximize sum of remaining elements after every removal of the array half with greater sum | C ++ 14 program to implement the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxweight ( int s , int e , unordered_map < int , int > & pre ) { if ( s == e ) return 0 ; int ans = 0 ; for ( int i = s ; i < e ; i ++ ) { int left = pre [ i ] - pre [ s - 1 ] ; int right = pre [ e ] - pre [ i ] ; if ( left < right ) ans = max ( ans , left + maxweight ( s , i , pre ) ) ; if ( left == right ) { ans = max ( { ans , left + maxweight ( s , i , pre ) , right + maxweight ( i + 1 , e , pre ) } ) ; } if ( left > right ) ans = max ( ans , right + maxweight ( i + 1 , e , pre ) ) ; } return ans ; } void maxSum ( vector < int > arr ) { unordered_map < int , int > pre ; pre [ -1 ] = 0 ; pre [ 0 ] = arr [ 0 ] ; for ( int i = 1 ; i < arr . size ( ) ; i ++ ) { pre [ i ] = pre [ i - 1 ] + arr [ i ] ; } cout << maxweight ( 0 , arr . size ( ) - 1 , pre ) ; } int main ( ) { vector < int > arr = { 6 , 2 , 3 , 4 , 5 , 5 } ; maxSum ( arr ) ; return 0 ; }