Given $n$ stacks of $k$ integers each. What is the maximum sum that can be achieved by removing exactly $p$ integers?
The following example illustrates the problem.
$n$ = 3, $k$ = 4, $p$ = 3
stack 1: 2, 5, 12, 5
stack 2: 10, 3, 12, 50
stack 3: 7, 4, 20, 20
Note that the top of a stack is the leftmost element.
Here, the optimal solution is to pick all the first three numbers from stack 3, which gives a sum of 31.
I came up with the following algorithm.
The idea is to calculate the best possible sum for each stack if all $p$ elements were chosen from that particular stack. This sum only considers the integers that can possibly be taken.
Then, greedily take the top element from the stack with the best possible sum. And update the sum for all stacks because now only $p-1$ integers need to be popped.
is this algorithm always going to produce a correct answer? If not, when would this fail?
I am aware that a dynamic programming solution can solve the problem in $O(npk)$ time.
This is based on the following problem from a previous contest on google coding competitions platform. (https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d40bb)