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 len of array is 1 ; Stores the readonly 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 readonly ans ; Function to print maximum sum ; To store prefix sums ; Traversing the array ; Add prefix sum of the array ; Driver code ; Function call
using System ; using System . Collections . Generic ; class GFG { static int maxweight ( int s , int e , Dictionary < 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 = 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 ; } static void maxSum ( List < int > arr ) { Dictionary < int , int > pre = new Dictionary < int , int > ( ) ; pre . Add ( - 1 , 0 ) ; pre . Add ( 0 , arr [ 0 ] ) ; for ( int i = 1 ; i < arr . Count ; i ++ ) { if ( pre [ i - 1 ] != 0 ) pre . Add ( i , pre [ i - 1 ] + arr [ i ] ) ; else pre . Add ( i , arr [ i ] ) ; } Console . WriteLine ( maxweight ( 0 , arr . Count - 1 , pre ) ) ; } public static void Main ( String [ ] args ) { List < int > arr = new List < int > ( ) ; arr . Add ( 6 ) ; arr . Add ( 2 ) ; arr . Add ( 3 ) ; arr . Add ( 4 ) ; arr . Add ( 5 ) ; arr . Add ( 5 ) ; maxSum ( arr ) ; } }