# Find the optimal partition in this matrix

Given a particular matrix of integers, the challenge is to draw a boundary line through the cells so that the sum of the numbers on the boundary line or above is as large as possible. In this case "above" means on the side including the top left cell. Here is an example non-optimal solution with everything on the boundary or above shaded in grey.

A boundary line should have the property that it is contiguous. This means that neighboring boundary cells should either be at the same y coordinate or one up or one down from the ones to their left and right.

The matrix you should do this with is:

[[ 3  0  2 -3 -3 -1 -2  1 -1  0]
[-1  0  0  0 -2 -3 -2  2 -2 -3]
[ 1  3  3  1  1 -3 -1 -1  3  0]
[ 0  0 -2  0  2  1  2  2 -1 -1]
[-1  0  3  1  1  3 -2  0  0 -1]
[-1 -1  1  2 -3 -2  1 -2  0  0]
[-3  2  2  3 -2  0 -1 -1  3 -2]
[-2  0  2  1  2  2  1 -1 -3 -3]
[-2 -2  1 -3 -2 -1  3  2  3 -3]
[ 2  3  1 -1  0  1 -1  3 -2 -1]]

• Shouldn't it be y-coordinate, given the description? Commented Dec 19, 2023 at 16:01
• @Someone Thank you. Fixed
– Simd
Commented Dec 19, 2023 at 16:56

I solved this as a shortest path problem in a directed network with a node for each cell, a source node, and a sink node. The arcs are from the source to cells $$(i,1)$$, from cell $$(i,j)$$ to $$(i',j+1)$$ with $$i'\in\{i-1,i,i+1\}$$, and from cells $$(i,10)$$ to the sink. The cost for an arc that enters cell $$(i,j)$$ is $$-\sum_{i'=1}^i a_{i'j}$$. Now find a shortest path from source to sink.