Maximize sum of topmost elements of S stacks by popping at most N elements | Python3 program to maximize the sum of top of the stack values of S stacks by popping at most N element ; Function for computing the maximum sum at the top of the stacks after popping at most N elements from S stack ; Constructing a dp matrix of dimensions ( S + 1 ) x ( N + 1 ) ; Loop over all i stacks ; Store the maximum of popping j elements up to the current stack by popping k elements from current stack and j - k elements from all previous stacks combined ; Store the maximum sum of popping N elements across all stacks ; dp [ S ] [ N ] has the maximum sum ; Driver code ; Number of stacks ; Length of each stack ; Maximum elements that can be popped
import sys NEW_LINE def maximumSum ( S , M , N , stacks ) : NEW_LINE INDENT dp = [ [ 0 for x in range ( N + 1 ) ] for y in range ( S + 1 ) ] NEW_LINE for i in range ( S ) : NEW_LINE INDENT for j in range ( N + 1 ) : NEW_LINE INDENT for k in range ( min ( j , M ) + 1 ) : NEW_LINE INDENT dp [ i + 1 ] [ j ] = max ( dp [ i + 1 ] [ j ] , stacks [ i ] [ k ] + dp [ i ] [ j - k ] ) NEW_LINE DEDENT DEDENT DEDENT result = - sys . maxsize - 1 NEW_LINE for i in range ( N + 1 ) : NEW_LINE INDENT result = max ( result , dp [ S ] [ i ] ) NEW_LINE DEDENT return result NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT S = 2 NEW_LINE M = 4 NEW_LINE stacks = [ [ 2 , 6 , 4 , 5 ] , [ 1 , 6 , 15 , 10 ] ] NEW_LINE N = 3 NEW_LINE print ( maximumSum ( S , M , N , stacks ) ) NEW_LINE DEDENT