python - 境界が既知の 2D 配列に対する Kadane のアルゴリズム

Question

Python 2 で既知の境界を持つ 2D 配列の Kadane アルゴリズムを実装しましたが、その実装をオンライン コンテストに使用していて、指定された時間よりも時間がかかります。

そのため、Kadane のアルゴリズムに似た複雑さの少ない別のアルゴリズムがあるかどうか、または私のコードを何らかの方法で最適化できるかどうかを考えさせられました。私の実装は、次元 x の任意の配列と次元NxMのサブ配列maxRowsに対して機能しmaxColsます。

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)

test.txt

4 8 2 3
1 1 2 3 3 1 1 1
2 2 2 2 2 2 2 2
3 3 3 1 1 3 3 4
0 0 1 1 3 2 2 1

で実行

python maxSumSubarray.py < test.txt

それは与えます

16

これは正しく、次の長方形です。

2 2 2
3 3 4

私は他の次元でも試しましたが、うまくいくと確信しています。唯一の問題は時間/複雑さです。どんな助けでも大歓迎です！御時間ありがとうございます。