Recursive algorithm to find maximum value in 2D array
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.