Kadane's Algorithm for 2D array with known boundaries

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

Run with

python maxSumSubarray.py < test.txt

i

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.

StackExchange Code Review Q#107033, answer score: 5