5
$\begingroup$

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.

enter image description here

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]]
$\endgroup$
2
  • $\begingroup$ Shouldn't it be y-coordinate, given the description? $\endgroup$
    – Someone
    Dec 19, 2023 at 16:01
  • $\begingroup$ @Someone Thank you. Fixed $\endgroup$
    – Simd
    Dec 19, 2023 at 16:56

1 Answer 1

4
$\begingroup$

The maximum sum is

11,

achieved, for example, by

enter image description here

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.

$\endgroup$
2
  • $\begingroup$ Would this allow a boundary that stopped at x=5 for example? $\endgroup$
    – Simd
    Dec 21, 2023 at 6:25
  • $\begingroup$ No, because only the rightmost cells have arcs to the sink node, and the path must go from source to sink. $\endgroup$
    – RobPratt
    Dec 21, 2023 at 13:26

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.