Which line is best?

Question

Consider an \$n \times n\$ grid of integers. The task is to draw a straight line across the grid so that the part that includes the top left corner sums to the largest number possible. Here is a picture of an optimal solution with score 45:

We include a square in the part that is to be summed if its middle is above or on the line. Above means in the part including the top left corner of the grid. (To make this definition clear, no line can start exactly in the top left corner of the grid.)

The task is to choose the line that maximizes the sum of the part that includes the top left square. The line must go straight from one side to another. The line can start or end anywhere on a side and not just at integer points.

The winning criterion is worst case time complexity as a function of \$n\$. That is using big Oh notation, e.g. \$O(n^4)\$.

Test cases

I will add more test cases here as I can.

The easiest test cases are when the input matrix is made of positive (or negative) integers only. In that case a line that makes the part to sum the whole matrix (or the empty matrix if all the integers are negative) wins.

Only slightly less simple is if there is a line that clearly separates the negative integers from the non negative integers in the matrix.

Here is a slightly more difficult example with an optimal line shown. The optimal value is 14.

The grid in machine readable form is:

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

Here is an example with optimal value 0.

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

Posted a question to cstheory about lower bounds for this problem.

Answer 1

Python3, O(n^4):

I'm not 100% sure this is correct, but I think at least the approach is solid and it seems to work OK.

import numpy as np
import fractions

def best_line(grid):
    n, m = grid.shape
    D = [(di, dj) for di in range(-(n - 1), n) for dj in range(-(n - 1), n)]
    def slope(d):
        di, dj = d
        if dj == 0:
            return float('inf') if di <= 0 else float('-inf'), -di
        else:
            return fractions.Fraction(di, dj), fractions.Fraction(-1, dj)
    D.sort(key=slope)
    D = np.array(D, dtype=np.int64)
    s_max = grid.sum()
    for grid in (grid, grid.T):
        left_sum = 0
        for j in range(grid.shape[1]):
            left_sum += grid[:,j].sum()
            for i in range(grid.shape[0]):
                p = np.array([i, j], dtype=np.int64)
                Q = p + D
                Q = Q[np.all((0 <= Q) & (Q < np.array(grid.shape)), axis=1)]
                s = left_sum 
                for q in Q:
                    if not np.any(q):
                        break
                    if q[1] <= j:
                        s -= grid[q[0],q[1]]
                    else:
                        s += grid[q[0],q[1]]
                    s_max = max(s_max, s)
    return s_max