Maximize sum of remaining elements after every removal of the array half with greater sum | C ++ program to implement the above approach ; Function to find the maximum sum ; Base Case ; Check if ( mapped key is found in the dictionary ; Traverse the array ; Store left prefix sum ; Store right prefix sum ; Compare the left and right values ; Store the value in dp array ; Return the final answer ; Function to print maximum sum ; Stores prefix sum ; Store results of subproblems ; Traversing the array ; Add prefix sum of array ; Print the answer ; Driver Code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 100 ] [ 100 ] ; int maxweight ( int s , int e , map < int , int > pre ) { if ( s == e ) return 0 ; if ( dp [ s ] [ e ] != -1 ) return dp [ s ] [ e ] ; 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 , ( int ) ( left + maxweight ( s , i , pre ) ) ) ; if ( left == right ) ans = max ( ans , max ( left + maxweight ( s , i , pre ) , right + maxweight ( i + 1 , e , pre ) ) ) ; if ( left > right ) ans = max ( ans , right + maxweight ( i + 1 , e , pre ) ) ; dp [ s ] [ e ] = ans ; } return dp [ s ] [ e ] ; } void maxSum ( int arr [ ] , int n ) { map < int , int > pre ; pre [ -1 ] = 0 ; pre [ 0 ] = arr [ 0 ] ; memset ( dp , -1 , sizeof dp ) ; for ( int i = 0 ; i < n ; i ++ ) pre [ i ] = pre [ i - 1 ] + arr [ i ] ; cout << ( maxweight ( 0 , n - 1 , pre ) ) ; } int main ( ) { int arr [ ] = { 6 , 2 , 3 , 4 , 5 , 5 } ; maxSum ( arr , 6 ) ; }