I asked this question first on StackOverflow but I didn't get an answer and was advised to try here too. So here we go.I have implemented Kadane's algorithm for a 2D array in Python 2 with known boundaries, but I'm using the implementation for an online contest and the time it takes is more than the time given.So that made me think if there is maybe another algorithm similar to Kadane's that has a smaller complexity, or if my code can be optimized in a way. My implementation works for any array with dimensions N x M and a subarray with dimensions maxRows x maxCols.maxSumSubarray.pyimport numpy as np# returns the maximum sum for the given vector using kadane's algorithm, with# maxRows maximum members in the sumdef 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 mline = 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.txt4 8 2 31 1 2 3 3 1 1 12 2 2 2 2 2 2 23 3 3 1 1 3 3 40 0 1 1 3 2 2 1Run withpython maxSumSubarray.py < test.txtit gives16which is correct and is the following rectangle:2 2 23 3 4I've tried with other dimensions too and I'm pretty sure it works fine. Only problem is time/complexity.
Kadane's Algorithm for 2D array with known boundaries
python;algorithm;python 2.7;matrix;numpy
Input can be simplified using destructuring assignment and NumPy:N, M, max_rows, max_cols = map(int, raw_input().split())table = np.genfromtxt(sys.stdin)By the PEP 8 standard, variable and function names should be written using lowercase_with_underscores.  The comment block for each function should be a docstring instead.The kadane2DwithBounds() function should return its result instead of printing it.The use of global variables N, M, table, and temp within the two functions is disconcerting.  table and temp should be passed explicitly.  N and M can be inferred by inspecting the table itself, and therefore don't need to be passed to the kadane functions.