Optimizing polygon

Question

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.

Answer 1

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.

Answer 2

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.