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
M and a subarray with dimensions
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 M = line maxRows = line maxCols = line table =  temp = np.empty(N, dtype = int) for _ in xrange(N): table.append(map(int, raw_input().split())) kadane2DwithBounds(maxRows, maxCols)
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
which is correct and is the following rectangle:
2 2 2 3 3 4
I've tried with other dimensions too and I'm pretty sure it works fine. Only problem is time/complexity.