Maximize the Sum of a Subsequence from an Array based on given conditions | Function to select the array elements to maximize the sum of the selected elements ; If the entire array is solved ; Memoized subproblem ; Calculate sum considering the current element in the subsequence ; Calculate sum without considering the current element in the subsequence ; Update the maximum of the above sums in the dp [ ] [ ] table ; Driver Code ; Initialize the dp array ; Function call
def maximumSum ( a , count , index , n , dp ) : NEW_LINE INDENT if ( index == n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ index ] [ count ] != - 1 ) : NEW_LINE INDENT return dp [ index ] [ count ] NEW_LINE DEDENT take_element = ( a [ index ] * count + maximumSum ( a , count + 1 , index + 1 , n , dp ) ) NEW_LINE dont_take = maximumSum ( a , count , index + 1 , n , dp ) NEW_LINE dp [ index ] [ count ] = max ( take_element , dont_take ) NEW_LINE return dp [ index ] [ count ] NEW_LINE DEDENT n = 5 NEW_LINE a = [ - 1 , - 9 , 0 , 5 , - 7 ] NEW_LINE dp = [ [ - 1 for x in range ( n + 1 ) ] for y in range ( n + 1 ) ] NEW_LINE print ( maximumSum ( a , 1 , 0 , n , dp ) ) NEW_LINE