如何加速800×800矩阵的最大和矩形求解算法？

我需要在大型整数矩阵中找到具有最大和的矩形。目前已有O(n³)时间复杂度的算法，这类算法逻辑可行，但受限于Python特性，运行速度偏慢——在我的PC上处理800×800的矩阵耗时56秒。想请教这段代码的提速空间有多大？

以下是我基于GeeksforGeeks代码编写的实现：

import numpy as np
def kadane(arr, start, finish, n):
    # initialize subarray_sum, max_subarray_sum and
    subarray_sum = 0
    max_subarray_sum = float('-inf')

    i = None
 
    # Just some initial value to check
    # for all negative values case
    finish = -1
 
    # local variable
    local_start = 0
 
    for i in range(n):
        subarray_sum += arr[i]
        if subarray_sum < 0:
            subarray_sum = 0
            local_start = i + 1
        elif subarray_sum > max_subarray_sum:
            max_subarray_sum = subarray_sum
            start = local_start
            finish = i

    # There is at-least one
    # non-negative number
    if finish != -1:
        return max_subarray_sum, start, finish
 
    # Special Case: When all numbers
    # in arr[] are negative
    max_subarray_sum = arr[0]
    start = finish = 0
    
    # Find the maximum element in array
    for i in range(1, n):
        if arr[i] > max_subarray_sum:
            max_subarray_sum = arr[i]
            start = finish = i
    return max_subarray_sum, start, finish
 
# The main function that finds maximum subarray_sum rectangle in M
def findMaxsubarray_sum(M):
    num_rows, num_cols = M.shape
 
    # Variables to store the final output
    max_subarray_sum, finalLeft = float('-inf'), None
    finalRight, finalTop, finalBottom = None, None, None
    left, right, i = None, None, None
 
    temp = [None] * num_rows
    subarray_sum = 0
    start = 0
    finish = 0
 
    # Set the left column
    for left in range(num_cols):
        # Initialize all elements of temp as 0
        temp = np.zeros(num_rows, dtype=np.int_)
        # Set the right column for the left
        # column set by outer loop
        for right in range(left, num_cols):
            temp += M[:num_rows, right]
            #print(temp, start, finish, num_rows)
            subarray_sum, start, finish = kadane(temp, start, finish, num_rows)
 
            # Compare subarray_sum with maximum subarray_sum so far.
            # If subarray_sum is more, then update maxsubarray_sum
            # and other output values
            if subarray_sum > max_subarray_sum:
                max_subarray_sum = subarray_sum
                finalLeft = left
                finalRight = right
                finalTop = start
                finalBottom = finish
 
    # final values
    print("(Top, Left)", "(", finalTop, finalLeft, ")")
    print("(Bottom, Right)", "(", finalBottom, finalRight, ")")
    print("Max subarray_sum is:", max_subarray_sum)

# np.random.seed(40)
square = np.random.randint(-3, 4, (800, 800))

# print(square)
%timeit findMaxsubarray_sum(square)

我想知道：

• 能否通过Numba、Pythran、并行化或优化Numpy使用等方式大幅提升运行速度？理想情况下希望把耗时控制在1秒以内。
• 有资料提到存在更快的算法，但不清楚实现难度如何。

测试用例1 #

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

正确答案：覆盖第一行的矩形，和为5。

测试用例2 #

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

正确答案：覆盖第二列的矩形，和为5。

测试用例3 #

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

正确答案：覆盖前两列的矩形，和为6。

内容的提问来源于stack exchange，提问作者Simd