Maximum subsequence sum possible by multiplying each element by its index | Initialize dp array ; Function to find the maximum sum of the subsequence formed ; Base Case ; If already calculated state occurs ; Include the current element ; Exclude the current element ; Update the maximum ans ; Function to calculate maximum sum of the subsequence obtained ; Print the maximum sum possible ; Given array ; Size of the array ; Function call
dp = [ [ - 1 for x in range ( 1005 ) ] for y in range ( 1005 ) ] NEW_LINE def maximumSumUtil ( a , index , count , n ) : NEW_LINE INDENT if ( index > n or count > n + 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ index ] [ count ] != - 1 ) : NEW_LINE INDENT return dp [ index ] [ count ] NEW_LINE DEDENT ans1 = ( maximumSumUtil ( a , index + 1 , count + 1 , n ) + a [ index ] * count ) NEW_LINE ans2 = maximumSumUtil ( a , index + 1 , count , n ) NEW_LINE dp [ index ] [ count ] = max ( ans1 , ans2 ) NEW_LINE return dp [ index ] [ count ] NEW_LINE DEDENT def maximumSum ( arr , N ) : NEW_LINE INDENT print ( maximumSumUtil ( arr , 0 , 1 , N - 1 ) ) NEW_LINE DEDENT arr = [ - 1 , 2 , - 10 , 4 , - 20 ] NEW_LINE N = len ( arr ) NEW_LINE maximumSum ( arr , N ) NEW_LINE