# Recursive algorithm to find maximum value in 2D array

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!

• 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.
– plop
Nov 1, 2020 at 12:21
• Sorry, I didn't specify that it is actually allowed to select 0 elements from a column. Nov 1, 2020 at 12:28
• Then above the $t$ is allowed to be $0$.
– plop
Nov 1, 2020 at 12:46
• Could you elaborate the approach, where t = 0, in the answer section, with some sort of a pseudo code algorithm? Thank you! Nov 1, 2020 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.