Maximizing sum of a spiral path on a grid

Question

Lets define a spiral path as one who movements are in a cycle of [right, down, left, up, right, down, left, up, ...] (note that you don't need to necessarily start with right, only that right must come after up, down after right, and so on). However, the path must not intersect with itself.

Given a grid, how would you find the maximum sum that can be attained by traversing such a path?

So for example, if the grid is

-5   -4   -3

 3     2    1

 -1    2    4

The spiral path that maximizes the sum is

-5   -4   -3

 3     2    1

 -1    2    4

The path goes like: {3, 2, 1, 4, 2}

---

My thinking is that this can be solved with some sort of prefix sum method, but I am not too sure on how to approach it. Another thought was just to run a depth-first-search from each point but that will be too inefficient of an algorithm.

Answer 1

Let's build the spiral outwards, in clockwise order (the counter-clockwise case works analogously). The state of the building process can be described by three variables:

• The bounding box of the spiral so far
• The current position
• The current direction (north, east, south, west)

We are allowed to make at most two different moves:

• go one step further in the current direction
• switch direction clockwise and go one step in the new direction. This is only allowed if we passed the borders of the bounding box already

There are O(n^4) bounding boxes and the current position is always at a border of the box, so this yields an O(n^5) time and space DP algorithm.

We can eliminate one dimension by noting that all but the last line segment we walk will completely cover the side of the current bounding box, so we can define f(x1, y1, x2, y2, d) as the maximum sum spiral with bounding box (x1, y1), (x2, y2) where the current positition is in the corner uniquely defined by the current position d.

The moves are then:

• Walk one step further in the current direction, extending the bounding box
• Switch the direction and walk all the way up to the end of the bounding box

For the second move we need to compute partial row and column sums in O(1), which is easy to do with some preprocessing. We also need to introduce a special case for the last segment of the spiral, because there we are allowed to not go up to the edge of the bounding box. The whole algorithm can be implemented in O(n^4).