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 ; 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
import java . util . * ; class solution { static int [ ] [ ] dp = new int [ 100 ] [ 100 ] ; static int maxweight ( int s , int e , HashMap < Integer , Integer > 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 . get ( i ) - pre . get ( s - 1 ) ; int right = pre . get ( e ) - pre . get ( i ) ; if ( left < right ) ans = Math . max ( ans , ( int ) ( 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 ) ) ; dp [ s ] [ e ] = ans ; } return dp [ s ] [ e ] ; } static void maxSum ( int arr [ ] , int n ) { HashMap < Integer , Integer > pre = new HashMap < Integer , Integer > ( ) ; pre . put ( - 1 , 0 ) ; pre . put ( 0 , arr [ 0 ] ) ; for ( int i = 0 ; i < 100 ; i ++ ) { for ( int j = 0 ; j < 100 ; j ++ ) dp [ i ] [ j ] = - 1 ; } for ( int i = 0 ; i < n ; i ++ ) pre . put ( i , pre . get ( i - 1 ) + arr [ i ] ) ; System . out . print ( ( maxweight ( 0 , n - 1 , pre ) ) ) ; } public static void main ( String args [ ] ) { int [ ] arr = { 6 , 2 , 3 , 4 , 5 , 5 } ; maxSum ( arr , 6 ) ; } }