0

我已经在 Python 2 中为具有已知边界的 2D 数组实现了 Kadane 算法，但我正在使用该实现进行在线竞赛，并且所花费的时间超过了给定的时间。

所以这让我想到是否可能有另一种类似于 Kadane 的算法具有更小的复杂性，或者我的代码是否可以以某种方式进行优化。我的实现适用于任何尺寸为Nx的数组M和一个尺寸为maxRowsx的子数组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)

测试.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

我也尝试过其他尺寸，我很确定它工作正常。唯一的问题是时间/复杂性。任何帮助，将不胜感激！谢谢你的时间。

4

0 回答 0