Maximize sum of topmost elements of S stacks by popping at most N elements | C ++ Program to maximize the sum of top of the stack values of S stacks by popping at most N elements ; 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 ) ; Initialize all states ; 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 Program ; Number of stacks ; Length of each stack ; Maximum elements that can be popped
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximumSum ( int S , int M , int N , vector < vector < int > > & stacks ) { int dp [ S + 1 ] [ N + 1 ] ; memset ( dp , INT_MIN , sizeof ( dp ) ) ; for ( int i = 0 ; i < S ; i ++ ) { for ( int j = 0 ; j <= N ; j ++ ) { for ( int k = 0 ; k <= min ( j , M ) ; k ++ ) { dp [ i + 1 ] [ j ] = max ( dp [ i + 1 ] [ j ] , stacks [ i ] [ k ] + dp [ i ] [ j - k ] ) ; } } } int result = INT_MIN ; for ( int i = 0 ; i <= N ; i ++ ) { result = max ( result , dp [ S ] [ i ] ) ; } return result ; } int main ( ) { int S = 2 ; int M = 4 ; vector < vector < int > > stacks = { { 2 , 6 , 4 , 5 } , { 1 , 6 , 15 , 10 } } ; int N = 3 ; cout << maximumSum ( S , M , N , stacks ) ; return 0 ; }