is there an efficient algorithm to find the optimal partition of a matrix?

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:

Is there an efficient algorithm for this optimization problem?

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.

StackExchange Computer Science Q#164612, answer score: 4