Introduction

The maximum-sum submatrix problem asks for a contiguous rectangular region in a 2D matrix whose elements add up to the largest possible value. The standard efficient solution is a 2D extension of Kadane's algorithm: fix a pair of row boundaries, compress the rows into a 1D array of column sums, and run the maximum-subarray algorithm on that array.

That turns a hard 2D search into a manageable series of 1D problems. It is much faster than checking every possible rectangle directly and is the usual interview or production answer when the matrix is dense.

Why the Naive Approach Is Too Slow

A submatrix is defined by four boundaries:

• top row
• bottom row
• left column
• right column

If you try every combination and sum the rectangle from scratch, the work grows too quickly. Even if prefix sums make each rectangle sum fast, you still have to examine all possible boundaries, which is too expensive for anything but small inputs.

The key optimization is to stop treating the full 2D rectangle as the primary unit of work.

Reduce the 2D Problem to Repeated 1D Problems

Fix a top row and a bottom row. For those row boundaries, each column can be collapsed into a single number: the sum of the entries in that column between those two rows.

Once you do that, the best left and right column boundaries are exactly the maximum-sum contiguous subarray of the collapsed array.

So the high-level strategy becomes:

1. choose a top row
2. extend the bottom row downward one row at a time
3. update a running array of column sums
4. run Kadane's algorithm on that array
5. keep the best rectangle seen so far

This reduces the time complexity to O(rows^2 * cols) when Kadane runs in O(cols).

Kadane's Algorithm with Coordinates

For this problem, Kadane's algorithm needs to return not just the best sum but also the start and end column indices.

1def kadane(arr):
2    best_sum = arr[0]
3    current_sum = arr[0]
4    best_left = best_right = 0
5    current_left = 0
6
7    for i in range(1, len(arr)):
8        if current_sum < 0:
9            current_sum = arr[i]
10            current_left = i
11        else:
12            current_sum += arr[i]
13
14        if current_sum > best_sum:
15            best_sum = current_sum
16            best_left = current_left
17            best_right = i
18
19    return best_sum, best_left, best_right

Starting from arr[0] rather than 0 is important because it handles the all-negative case correctly.

Full 2D Solution in Python

1def max_sum_submatrix(matrix):
2    rows = len(matrix)
3    cols = len(matrix[0])
4
5    best_sum = matrix[0][0]
6    best_coords = (0, 0, 0, 0)  # top, left, bottom, right
7
8    for top in range(rows):
9        temp = [0] * cols
10
11        for bottom in range(top, rows):
12            for col in range(cols):
13                temp[col] += matrix[bottom][col]
14
15            current_sum, left, right = kadane(temp)
16
17            if current_sum > best_sum:
18                best_sum = current_sum
19                best_coords = (top, left, bottom, right)
20
21    return best_sum, best_coords
22
23
24matrix = [
25    [1, -2, -1, 4],
26    [-8, 3, 4, 2],
27    [3, 8, 10, -8],
28    [-4, -1, 1, 7],
29]
30
31best_sum, coords = max_sum_submatrix(matrix)
32print(best_sum)
33print(coords)

This returns both the maximum sum and the rectangle coordinates.

Reconstruct the Rectangle

If you need the actual submatrix values, use the saved coordinates.

1def extract_submatrix(matrix, top, left, bottom, right):
2    return [row[left:right + 1] for row in matrix[top:bottom + 1]]
3
4sub = extract_submatrix(matrix, *coords)
5print(sub)

That separation is useful because some callers only need the score, while others need the rectangle contents too.

Complexity and Practical Notes

If there are r rows and c columns, the row-compression approach is O(r^2 * c) and uses O(c) extra space for the temporary column-sum array.

If the matrix is much wider than it is tall, you can transpose the idea and compress columns instead. The algorithm stays the same conceptually, but you choose the smaller dimension for the squared outer loop when possible.

Common Pitfalls

The biggest mistake is using a Kadane implementation that resets the running sum to zero unconditionally, which fails for all-negative matrices. Another is recomputing the collapsed column sums from scratch for every row pair instead of updating them incrementally. Developers also often forget to track the rectangle coordinates and end up with only the sum when the problem requires the actual submatrix. Finally, when the matrix can be empty, the code should validate input before indexing matrix[0].

Summary

• The efficient solution is a 2D extension of Kadane's algorithm.
• Fix row pairs, compress them into a 1D column-sum array, and run Kadane on that array.
• The resulting complexity is O(rows^2 * cols).
• Track coordinates along with the best sum if you need the rectangle itself.
• Handle all-negative inputs and empty-input validation carefully.