已知边界二维阵列的Kadane算法

Question

我已经在python2中实现了一个2D数组的Kadane算法，但是我将这个实现用于一个在线竞赛，它所花费的时间比给定的时间要多。在

所以这让我想到，是否有另一种类似于Kadane的算法具有更小的复杂度，或者我的代码是否可以在某种程度上得到优化。我的实现适用于任何维数为NxM的数组和维数为maxRowsxmaxCols的子数组。在

maxSumSubarray.py 在

import numpy as np

# returns the maximum sum for the given vector using kadane's algorithm, with
# maxRows maximum members in the sum
def kadane1DwithBounds(maxRows):
    global temp
    m = s = sum(temp[i] for i in xrange(maxRows))
    k = 0

    for i in xrange(1, N - maxRows + 1):
        s -= temp[k]
        s += temp[maxRows + i - 1]
        k += 1
        m = max(m, s)

    return m

# prints the maximum "area" given by the values of an NxM array inside a
# subarray with dimensions maxRows x maxCols. temp holds the latest vector to be
# given to kadane1DwithBounds()
def kadane2DwithBounds(maxRows, maxCols):
    global temp
    for i in xrange(N):
        temp[i] = sum(table[i][j] for j in xrange(maxCols))

    m = kadane1DwithBounds(maxRows)

    k = 0
    for j in xrange(1, M - maxCols + 1):
        for i in xrange(N):
            temp[i] -= table[i][k]
            temp[i] += table[i][maxCols + j - 1]
        k += 1
        m = max(m, kadane1DwithBounds(maxRows))

    print m

line = map(int, raw_input().split())
N = line[0]
M = line[1]
maxRows = line[2]
maxCols = line[3]

table = []
temp = np.empty(N, dtype = int)

for _ in xrange(N):
    table.append(map(int, raw_input().split()))

kadane2DwithBounds(maxRows, maxCols)

测试.txt

^{pr2}$

与…一起跑

python maxSumSubarray.py < test.txt

它给予

16

它是正确的，是下面的矩形：

2 2 2
3 3 4

我也尝试过其他维度，我很确定它工作得很好。唯一的问题是时间/复杂性。任何帮助都将不胜感激！谢谢你的时间。在