3
$\begingroup$

Consider an $n \times n$ matrix of integers. Define a boundary in the matrix to be a sequence of cells, one per x-coordinate, where the y-coordinates of the boundary either stay the same or go up/down by one for successive values on the x-axis. I would like to find a boundary that maximizes the sum of the cell values on the boundary or "above" it. Here, above means on the side that includes the top left cell. Here is a picture of a non-optimal solution:

enter image description here

Is there an efficient algorithm for this optimization problem?

$\endgroup$

1 Answer 1

4
$\begingroup$

Call your matrix $A$ and define $S(r,c) := \sum_{1\leq i\leq r}A_{i,c}$.

Now call $D(r,c)$ the optimal value for the submatrix consisting of the first $c$ columns of $A$, for a path which ends at row $r$. For convenience, define $D(r,0):=0$ for all $1\leq r \leq n$ and $D(0,c):=DC(n+1,c)=\infty$ for all $1\leq c \leq n$.

Then, for all $1 \leq c,r \leq n$, we have $$D(r,c) = S(r,c) + \max\{D(r-1,c-1),D(r,c-1), D(r+1,c-1)\}.$$ This leads to a $O(n^2)$ time dynamic programming algorithm to find the optimal value, which is $\max_{1\leq i \leq n}D(i,n)$.

I leave it as an exercise to you to work out the details, and modify the algorithm so that you not only get the value of an optimal path, but an optimal path itself.

$\endgroup$
2
  • $\begingroup$ Thank you. It's clear how this works now. $\endgroup$
    – Simd
    Dec 20, 2023 at 14:38
  • $\begingroup$ Is DC a typo in DC(n+1, c)? $\endgroup$
    – Simd
    Feb 2 at 16:34

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.