Maximize sum of remaining elements after every removal of the array half with greater sum | Function to find the maximum sum ; Base Case ; Create a key to map the values ; 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
def maxweight ( s , e , pre , dp ) : NEW_LINE INDENT if s == e : NEW_LINE INDENT return 0 NEW_LINE DEDENT key = ( s , e ) NEW_LINE if key in dp : NEW_LINE INDENT return dp [ key ] NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( s , e ) : NEW_LINE INDENT left = pre [ i ] - pre [ s - 1 ] NEW_LINE right = pre [ e ] - pre [ i ] NEW_LINE if left < right : NEW_LINE INDENT ans = max ( ans , left + maxweight ( s , i , pre , dp ) ) NEW_LINE DEDENT if left == right : NEW_LINE INDENT ans = max ( ans , left + maxweight ( s , i , pre , dp ) , right + maxweight ( i + 1 , e , pre , dp ) ) NEW_LINE DEDENT if left > right : NEW_LINE ans = max ( ans , right + maxweight ( i + 1 , e , pre , dp ) ) NEW_LINE dp [ key ] = ans NEW_LINE DEDENT return dp [ key ] NEW_LINE DEDENT def maxSum ( arr ) : NEW_LINE INDENT pre = { - 1 : 0 , 0 : arr [ 0 ] } NEW_LINE dp = { } NEW_LINE for i in range ( 1 , len ( arr ) ) : NEW_LINE INDENT pre [ i ] = pre [ i - 1 ] + arr [ i ] NEW_LINE DEDENT print ( maxweight ( 0 , len ( arr ) - 1 , pre , dp ) ) NEW_LINE DEDENT arr = [ 6 , 2 , 3 , 4 , 5 , 5 ] NEW_LINE maxSum ( arr ) NEW_LINE