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
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
global temp
for i in xrange(N):
temp[i] = sum(table[i][j] for j in xrange(maxCols))

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

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()))



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


it gives

16


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.

• In addition to (hopefully) suggestions to improve time/complexity, are you also interested in improvement ideas for other aspects of your code? (That's what we normally do here: review any aspect) – janos Oct 9 '15 at 8:06
• Yes of course. That's why I thought to ask first on SO. If there is a more efficient method or a better implementation I would be really glad to see it. – ChrisG Oct 9 '15 at 8:08
• That's fantastic, welcome to Code Review! – janos Oct 9 '15 at 8:27

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.

• N, M, maxCols, and maxRows are passed because that's what the specification asks. As of the part of code that deals with the input was not included in the main code. The functions are a part of a bigger project which does read in a numpy array, but I didn't include it and used a really simplified version . Other than that your point on the global variables, the names of the variables and the function comment blocks are great advice. Thanks! Although that doesn't really make the usage of the code more efficient. So I'll wait for a better answer. Thanks for the advice though! – ChrisG Oct 9 '15 at 9:37

Getting rid of the manual index k which is unnecessary:

def kadane1DwithBounds(maxRows):
global temp

m = s = sum(temp[i] for i in xrange(maxRows))
for i in xrange(N - maxRows):
s += temp[maxRows + i] - temp[i]
if s > m:
m = s
return m

global temp

for i in xrange(N):
temp[i] = sum(table[i][j] for j in xrange(maxCols))

for j in xrange(M - maxCols):
for i in xrange(N):
delta = table[i][maxCols + j] - table[i][j]
temp[i] += delta
return m


Testing this on a 36x72 matrix with a 6x4 submatrix the new routines take about 68% of the original ones, so roughly minus one third.

This program computes sums over a sliding window of fixed size, and takes the maximal sum. This is not Kadane's algorithm, which solves the more difficult problem where the size of the subarray is not predefined.

To improve performance, you should take better advantage of NumPy. Avoid Python loops by vectorized operations. Using numpy.cumsum over the full 2D array would be a good starting point.

Here's how you could vectorize kadane1DwithBounds. I changed naming as well. From the cumulative sums you can get the sliding sums by subtracting at an offset. The advantage over your version is that the Python for loop is replaced by array operations that are implemented in C. If you are not familiar with the concept, I suggest reading the What is NumPy? page.

def max_sliding_sum(array, window_size):
cum_sum = np.cumsum(array)
sliding_sum = cum_sum[window_size:] - cum_sum[:-window_size]
return sliding_sum.max()

• Yes you've got a point that this is not truly Kadane's algorithm but I named it so for lack of a better name, and because I got the idea of how to compute the sum from said algorithm. Other than that could you elaborate a little more how would cumsum() make things better? Wouldn't it recalculate previously calculated sums? (something that I get around using the for loop, subtracting the first element and adding the next one). – ChrisG Oct 9 '15 at 18:47
• @ChrisG See edit, and do read up on NumPy. It can give huge speedups for this type of code. – Janne Karila Oct 10 '15 at 9:09

Vanilla python 3 implementation based on suggestions and answers so far:

def kadane_bound(rows, row_boundary):
"""
Find the largest sum in a contiguous subarray.
"""
maximum_sum = current_sum = sum(temp[i] for i in range(row_boundary))

for i in range(rows - row_boundary):
current_sum += temp[row_boundary + i] - temp[i]
if current_sum > maximum_sum:
maximum_sum = current_sum
return maximum_sum

def kadane_matrix_bound(matrix, rows, columns, row_boundary, column_boundary):
"""
Compute maximum sum over a sliding window of fixed size.
"""
for i in range(rows):
temp[i] = sum(matrix[i][j] for j in range(column_boundary))

for j in range(columns - column_boundary):
for i in range(rows):
delta = matrix[i][column_boundary + j] - matrix[i][j]
temp[i] += delta
return maximum_sum

def parse_input():
line = list(map(int, input().split()))
rows, columns, max_rows, max_cols = line[0], line[1], line[2], line[3]
global temp
temp = [0] * rows
matrix = []
for _ in range(rows):
matrix.append(list(map(int, input().split())))
return matrix, rows, columns, max_rows, max_cols

def main():
matrix, rows, columns, max_rows, max_cols = parse_input()
maximum_submatrix_sum = kadane_matrix_bound(matrix, rows, columns, max_rows, max_cols)
print(maximum_submatrix_sum)

if __name__ == '__main__':
main()
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.3036053776741028, "perplexity": 2347.7936605158734}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2021-21/segments/1620243991224.58/warc/CC-MAIN-20210516140441-20210516170441-00155.warc.gz"}