When does this algorithm fail?

Question

The problem

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.

The algorithm

I came up with the following algorithm.

enter image description here

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.

The question

is this algorithm always going to produce a correct answer? If not, when would this fail?

Disclaimer

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)

• D.W.: cs.stackexchange.com/q/59964/755
• D.W.: Can you credit the original source for this?
• JhonRM: @D.W This is based on the following problem from a previous contest on google coding competitions platform. (codingcompetitions.withgoogle.com/kickstart/round/…)

Answer 1

Here is a counterexample, with $p = 2$:

• stack 1: 600,600ドル$.
• stack 2: 1000,0ドル$.
• stack 3: 1000,0ドル$.

Your algorithm will choose the top element from stack 1 and one of the top elements from the other stacks, but it is better to choose the top elements of stack 2 and stack 3.

Disclaimer: This is based on your description of the algorithm. I don't understand some of the notation in the algorithm itself.

• Yuval Filmus: Oops, I was thinking about minimizing the sum. Let me redo the example.
• JhonRM: could you explain what is not clear in the notation? so that I can fix it.
• Yuval Filmus: For example, the definition of $R_i$ is unclear. I guess you mean that initially, $l = 0$ and $r = \min(k-1,p-1)$. Then, $S$ is undefined. It is probably just the collection of all $S_i$.
• Yuval Filmus: Updated my example.
• JhonRM: Yes, that is what I meant. I will try to make that clear. Thank you for your feedback