Kadane's Algorithm for 2D array with known boundaries

Question

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

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.

Answer 1

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.

Answer 2

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

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)
    for j in xrange(M - maxCols):
        for i in xrange(N):
            delta = table[i][maxCols + j] - table[i][j]
            temp[i] += delta
        m = max(m, kadane1DwithBounds(maxRows))
    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.

Answer 3

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

Answer 4

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

    maximum_sum = kadane_bound(rows, row_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
        maximum_sum = max(maximum_sum, kadane_bound(rows, row_boundary))
    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()