Introduction

The maximum-sum subrectangle problem asks for the axis-aligned rectangle inside a matrix whose entries add up to the largest possible value. In dense matrices, the classic solution is a two-dimensional form of Kadane’s algorithm. In sparse matrices, the same core idea still matters, but you gain extra leverage by avoiding needless work on the many zero entries.

Dense Baseline: 2D Kadane

The standard dense solution fixes a left column and a right column, compresses everything between them into a one-dimensional row-sum array, and then runs Kadane’s maximum-subarray algorithm on that array.

If the matrix has R rows and C columns, this gives a typical time cost of O(C^2 * R) or O(R^2 * C) depending on which dimension you compress.

Kadane for one dimension:

1def kadane(arr):
2    best = arr[0]
3    current = arr[0]
4    start = end = temp_start = 0
5
6    for i in range(1, len(arr)):
7        if current < 0:
8            current = arr[i]
9            temp_start = i
10        else:
11            current += arr[i]
12
13        if current > best:
14            best = current
15            start = temp_start
16            end = i
17
18    return best, start, end

That one-dimensional routine is the engine inside the 2D solution.

Sparse Matrices Change the Engineering Tradeoff

If most entries are zero, converting the whole matrix to dense form and scanning every cell may waste a lot of time and memory. The key sparse insight is that zero entries do not need to be stored explicitly, and row accumulations only need to change when a nonzero element contributes inside the active column range.

There are two broad cases:

• the matrix dimensions are moderate, but values are mostly zero
• the matrix dimensions are huge, and only a small set of coordinates are nonzero

In the first case, a sparse-friendly accumulation strategy often helps. In the second, coordinate compression becomes much more important.

Practical Sparse-Friendly Approach

Suppose the matrix is stored row by row as dictionaries of nonzero columns. Then for each left-right column pair, you only add entries that actually exist in that range.

A simple representation:

1sparse_rows = [
2    {1: 5, 4: -2},
3    {0: -1, 3: 4},
4    {2: 7},
5    {1: -3, 4: 6},
6]

A sparse-friendly implementation can look like this:

1def max_sum_subrectangle_sparse(sparse_rows, num_cols):
2    num_rows = len(sparse_rows)
3    best_sum = float("-inf")
4    best_rect = None
5
6    for left in range(num_cols):
7        row_sums = [0] * num_rows
8
9        for right in range(left, num_cols):
10            for r, row in enumerate(sparse_rows):
11                row_sums[r] += row.get(right, 0)
12
13            current_sum, top, bottom = kadane(row_sums)
14            if current_sum > best_sum:
15                best_sum = current_sum
16                best_rect = (top, left, bottom, right)
17
18    return best_sum, best_rect

This still follows the dense algorithm’s structure, but it uses sparse row storage so the matrix itself is not stored densely.

Coordinate Compression for Very Large Sparse Grids

If row and column indices are very large but only a few positions are nonzero, another useful technique is coordinate compression.

The idea is:

• collect all rows and columns that contain nonzero values
• map them into a smaller dense index space
• solve the problem on the compressed grid

This does not eliminate all complexity, but it can reduce a huge mostly empty problem into one whose effective size matches the nonzero structure rather than the raw coordinate range.

The catch is that compression must preserve rectangle semantics correctly. That makes the implementation more subtle than ordinary sparse storage.

Watch the All-Negative Case

The maximum rectangle is not always a large region. If every value is negative, the correct answer is the least negative single cell.

That is why Kadane’s implementation must be written carefully. A version that resets to zero blindly can produce the wrong answer on all-negative input.

Choosing the Compression Dimension

In the dense algorithm, you usually compress the smaller dimension to reduce work. The same idea still applies here. If there are far fewer rows than columns, compress over columns and run Kadane on rows. If the opposite is true, transpose the logic.

This choice affects constant factors a lot even when the asymptotic formula looks similar.

Common Pitfalls

The most common mistake is assuming sparsity automatically changes the asymptotic problem completely when the basic left-right compression logic is still the right foundation. Another is writing a Kadane implementation that fails on all-negative row sums. Developers also often store sparse data efficiently but then immediately densify the entire matrix and lose the advantage. A final issue is forgetting to choose the compression direction based on the smaller effective dimension, which makes the implementation slower than necessary.

Summary

• The classic solution is 2D Kadane: compress one dimension and run maximum subarray on the other.
• Sparse matrices help mainly by reducing storage and avoiding needless zero handling.
• Sparse row or coordinate-based representations can make the implementation more practical.
• Kadane must handle all-negative cases correctly.
• For very large sparse coordinate spaces, coordinate compression may be necessary before solving the rectangle problem efficiently.