Imagine a 2D array of size n x m, where every column is a stack of positive values. I am trying to figure out a recursive pseudo code algorithm, where I have a number k, that is the maximum number of elements to pick from the array, which would find the indices in every column, that would maximise the sum of all the values of that index and all values above it.

[5 7 8]
[2 0 1]
[1 4 3]

For example here, if I took the number k to be 4 then I could only pick 4 values, s.t. the sum of them is maximised. For example, index 1 in the first column (value 2), index 0 in the second (value 7) and third column (value 8), which would result in

5 + 2 + 7 + 8

But I cannot grasp how could I implement the recursive algorithm to solve an issue like this. Would be grateful for any directions on this matter.

Thank you!

  • $\begingroup$ I don't know if one is allowed to pick zero elements from a column or not. I am assuming in the following that we choose at least one, but change accordingly. In the first column you can choose the first element, or the second, ..., or the $\min(n,k)$. For the choice $t$, then you solve the problem $n\times (m-1)$ and $k-t$ and add its solution with the sum of the $t$ elements chosen in the first column. Return the maximum among all the choices of $t$ with the corresponding solution of the subproblem $n\times(m-1)$, $k-t$. I make no claim about efficiency, only that it is a recursive solution. $\endgroup$ – plop Nov 1 '20 at 12:21
  • $\begingroup$ Sorry, I didn't specify that it is actually allowed to select 0 elements from a column. $\endgroup$ – memory_dump Nov 1 '20 at 12:28
  • $\begingroup$ Then above the $t$ is allowed to be $0$. $\endgroup$ – plop Nov 1 '20 at 12:46
  • $\begingroup$ Could you elaborate the approach, where t = 0, in the answer section, with some sort of a pseudo code algorithm? Thank you! $\endgroup$ – memory_dump Nov 1 '20 at 18:17

You can solve this using dynamic programming. For each $i$ and $\ell \leq k$, find the best solution for the first $i$ columns, when you are allowed to pick at most $\ell$ values.

  • $\begingroup$ I want to solve it with through a recursive way, not using DP. $\endgroup$ – memory_dump Nov 1 '20 at 16:03
  • $\begingroup$ Dynamic programming is an efficient implementation of recursion, when identical subproblems are only computed once. $\endgroup$ – Yuval Filmus Nov 1 '20 at 16:19
  • $\begingroup$ Could you just elaborate this approach a bit more, so that I can understand what for loops to use here and mark the answer as correct - thank you! $\endgroup$ – memory_dump Nov 20 '20 at 10:25
  • $\begingroup$ I'm not giving the full details on principle. $\endgroup$ – Yuval Filmus Nov 20 '20 at 11:18
  • $\begingroup$ I don't understand the point of your principle if someone cannot fully understand your answer to a given question. "Find best solution for the first i columns" is like "Find the best food in Vietnam", there are hundreds of questions and implications related to it. But fine, you keep believing in your principles. $\endgroup$ – memory_dump Nov 20 '20 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.