# 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.

• Thank you. It's clear how this works now.
– Simd
Dec 20, 2023 at 14:38
• Is DC a typo in DC(n+1, c)?
– Simd
Feb 2 at 16:34
The text passage describes a problem of finding an optimal boundary in an \(n \times n\) matrix that maximizes the sum of the cell values on the boundary or "above" it. It then provides a dynamic programming solution to solve this optimization problem.
single_question_with_answer
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# 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.

• Thank you. It's clear how this works now.
– Simd
Dec 20, 2023 at 14:38
• Is DC a typo in DC(n+1, c)?
– Simd
Feb 2 at 16:34
user
The text passage describes a problem of finding an optimal boundary in an \(n \times n\) matrix that maximizes the sum of the cell values on the boundary or "above" it. It then provides a dynamic programming solution to solve this optimization problem.

TYPE: SINGLE_QUESTION_WITH_ANSWER