Maximize sum of remaining elements after every removal of the array half with greater sum | Java 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 ; To store prefix sums ; Traversing the array ; Add prefix sum of the array ; Driver code ; Function call
import java . util . * ; class GFG { static int maxweight ( int s , int e , Map < Integer , Integer > pre ) { if ( s == e ) return 0 ; int ans = 0 ; for ( int i = s ; i < e ; i ++ ) { int left = pre . get ( i ) - pre . get ( s - 1 ) ; int right = pre . get ( e ) - pre . get ( 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 < Integer > arr ) { Map < Integer , Integer > pre = new HashMap < > ( ) ; pre . put ( - 1 , 0 ) ; pre . put ( 0 , arr . get ( 0 ) ) ; for ( int i = 1 ; i < arr . size ( ) ; i ++ ) { pre . put ( i , pre . getOrDefault ( i - 1 , 0 ) + arr . get ( i ) ) ; } System . out . println ( maxweight ( 0 , arr . size ( ) - 1 , pre ) ) ; } public static void main ( String [ ] args ) { List < Integer > arr = Arrays . asList ( 6 , 2 , 3 , 4 , 5 , 5 ) ; maxSum ( arr ) ; } }