# Maximum pentagon sum

For this problem you are given an $$\n \times n\$$ matrix of integers. The task is to find a pentagon in the matrix with maximum sum. The pentagon must include part (or all) of the x and y axes as two of its sides starting from the top left cell.

All the sides except one must be horizontal or vertical. The remaining side is at 45 degrees ( that is it goes up one for each step to the right).

This picture shows a matrix with a pentagonal part shaded.

Either one or two of the sides can have length zero, as in this example where two zero length sides have turned the pentagon into a triangle. This is an optimal triangular solution for this matrix but may not be an optimal pentagon.

Or this example where one zero-length side has turned a pentagon into a rectangle. This happens to be the optimal rectangle but may not be an optimal pentagon.

[[ 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]]


The winning criterion is asymptotic time complexity. E.g. $$\O(n^2)\$$ time.

# Python, $$\\mathcal O(n^2)\$$

def best_pentagon(grid):
best = float("-inf"), -1, -1, -1
rects = [0] * len(grid[0])
pents = [(0, 0)] * len(grid[0])
for y, row in enumerate(grid):
line = 0
lines = [line := line + value for value in row]
rects = [rect + line for rect, line in zip(rects, lines)]
pents = [
max((rect, y), (pent + line, z))
for rect, (pent, z), line in zip(rects, pents[1:], lines)
] + [(rects[-1], y)]
best = max(best, max((pent, x, y, z) for x, (pent, z) in enumerate(pents)))
return best


Attempt This Online!

Returns a tuple (sum, x, y, z) for a pentagon summing to sum whose bottom row ends at $$\(x, y)\$$ and whose rightmost column ends at $$\(x + y - z, z)\$$.

### How it works

A pentagon whose bottom row ends at $$\(x, y)\$$ is either

• the rectangle with corner $$\(x, y)\$$, or
• the union of the partial row $$\(0, y)…(x, y)\$$ with a pentagon whose bottom row ends at $$\(x + 1, y - 1)\$$.

This leads to a straightforward dynamic programming solution.

• This is really elegant and smart. How can I print out the optimal pentagon found? The final value of pentagons is "0 -15" for the last example I gave but I don't know how to interpret it.
– Simd
Dec 21, 2023 at 9:33
• @Simd I don’t know where you got “0 -15”, but I’ve updated the solution to return the pentagon’s coordinates. Dec 21, 2023 at 18:56

# Python, $$\\mathcal{O}(n^2)\$$ time (optimal)

def solve(n, grid):
# Pad the given grid with zeros to form a right triangle.
# Note that any pentagonal region in this triangle can be truncated
# to a valid pentagonal region within the original grid,
# by stripping away the padded zeros,
# so if we solve the maximum pentagon problem within this triangle,
# we get a valid solution for the grid.
# This is done to simplify coding. It adds some constant factor
# but doesn't change the overall time complexity.
triangle = [row[:] for row in grid]
for r in range(n-1):
triangle[r] += [0] * (n-1-r)
triangle.append([0] * (n-1-r))
m = n * 2 - 1 # size of the triangle

# Calculate cumulative sums in two directions: rightward and downward.
right_cumsum = [row[:] for row in triangle]
down_cumsum = [row[:] for row in triangle]
for r in range(m):
for c in range(1, m - r):
right_cumsum[r][c] += right_cumsum[r][c-1]
for r in range(1, m):
for c in range(m - r):
down_cumsum[r][c] += down_cumsum[r-1][c]

# We solve the pentagon problem by first forming a large triangle
# containing the upper left corner, and truncating smaller triangles
# from the rightmost and downmost ends.
ans = float('-inf')
for t in range(1, m+1):
# From the cumulative sums calculated above, we can get the sums of
# horizontal strips and vertical strips that form the triangle.
# The cumulative sum of the horizontal strips gives all possible cutaways
# from the bottom; that of vertical strips gives those from the right.

# vertical_strips[k] == sum of k vertical strips from upper right
# horizontal_strips[k] == sum of k horizontal strips from lower left
vertical_strips = [0] + [down_cumsum[i][t-1-i] for i in range(t)]
horizontal_strips = [0] + [right_cumsum[t-1-i][i] for i in range(t)]
for i in range(1, t+1):
vertical_strips[i] += vertical_strips[i-1]
horizontal_strips[i] += horizontal_strips[i-1]
triangle_sum = horizontal_strips[t]

# Now, for each possible cutaway from the bottom, we will find the
# smallest valid cutaway from the right (so we get the maximum sum
# for the given triangle size and bottom cut size).
# When k horizontal strips are cut, valid cuts from the right are
# zero to t-k vertical strips (inclusive).
# Minimum of these values can be preprocessed in O(m) via cumulative minimum.
# To make sure that the top left cell is included, k goes up to t-1.
for i in range(1, t+1):
vertical_strips[i] = min(vertical_strips[i], vertical_strips[i-1])
for k in range(0, t):
cur_area = triangle_sum - horizontal_strips[k]
max_area = cur_area - vertical_strips[t-k]
ans = max(ans, max_area)
return ans


Attempt This Online!

This is an art of cumulative operations lol. This is optimal in terms of asymptotic time complexity because you need $$\\mathcal{O}(n^2)\$$ time just to observe all the elements in the matrix.

• This is great. How can I see what the optimal pentagon is?
– Simd
Dec 21, 2023 at 9:26