0
$\begingroup$

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!

Improve this question
$\endgroup$
4
  • $\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
    Commented Nov 1, 2020 at 12:21
  • $\begingroup$ Sorry, I didn't specify that it is actually allowed to select 0 elements from a column. $\endgroup$
    – memory_dump
    Commented Nov 1, 2020 at 12:28
  • $\begingroup$ Then above the $t$ is allowed to be $0$. $\endgroup$
    – plop
    Commented Nov 1, 2020 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
    Commented Nov 1, 2020 at 18:17

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I want to solve it with through a recursive way, not using DP. $\endgroup$
    – memory_dump
    Commented Nov 1, 2020 at 16:03
  • $\begingroup$ Dynamic programming is an efficient implementation of recursion, when identical subproblems are only computed once. $\endgroup$
    – Yuval Filmus
    Commented Nov 1, 2020 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
    Commented Nov 20, 2020 at 10:25
  • $\begingroup$ I'm not giving the full details on principle. $\endgroup$
    – Yuval Filmus
    Commented Nov 20, 2020 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
    Commented Nov 20, 2020 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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