Maximum Sum Rectangle in Image

1. Background Knowledge

The Maximum Sum Rectangle problem extends the classic 1D Maximum Subarray Sum problem to 2D matrices with possibly negative values. In 1D, Kadane's algorithm finds the contiguous subarray with maximum sum in $O(n)$ time by tracking the maximum suffix sum while scanning.

In 2D, we seek a sub-rectangle $(i_1 \leq i \leq i_2, j_1 \leq j \leq j_2)$ maximizing $\sum_{i=i_1}^{i_2}$\sum_{j=j_1}^{j_2}$matrix[i][j]$. Negative values require checking the empty rectangle (sum 0), but constraints imply non-empty solutions are feasible. This is NP-hard in general geometric settings, but the fixed-size grid enables dynamic programming.

Prerequisites:

• Prefix sums for $O(1)$ range queries: $prefix[i+1][j+1] = matrix[i][j] + prefix[i][j+1] + prefix[i+1][j] - prefix[i][j]$
• Understanding Kadane's algorithm as a 1D DP: $max_ending_here[i] = \max(matrix[i], max_ending_here[i-1] + matrix[i])$

2. Algorithm Approach

Standard O(N³) Solution: Fix left/right column pairs $(l, r)$, create a 1D "height" array where $temp[i] =$ sum of row $i$ from columns $l$ to $r$, then apply Kadane's on $temp$ to find best row range. Repeat for all $O(N^2)$ column pairs.

Alternatives:

• "Sliced" subwindow search for sublinear approximations on natural images
• Branch-and-bound or geometric methods for sparse/special cases

For constraints $N \leq 100$, O(N³) = 10⁶ operations is optimal.

3. Step-by-Step Strategy

1. Precompute prefix sums (optional, but using temp sums directly is equivalent):

for l = 0 to cols-1
initialize temp[rows] = {0}
for r = l to cols-1
for i = 0 to rows-1
temp[i] += matrix[i][r]
max_rectangle = max(max_rectangle, kadane(temp))

2. Kadane's 1D on temp[] (handles negatives correctly):

int kadane(vector<int>& arr) {
int max_so_far = INT_MIN, max_ending_here = 0;
for (int x : arr) {
max_ending_here = max(x, max_ending_here + x);
max_so_far = max(max_so_far, max_ending_here);
}
return max_so_far;
}

Initialize max_so_far = 0 if empty rectangle allowed.

3. Track global maximum across all $(l,r)$ pairs.

4. Edge cases: All-negative matrix (return max element), 1x1 matrix, empty sub-rectangle.

4. Common Pitfalls

• Forgetting negatives in Kadane: Must reset max_ending_here = 0 (or max element) when prefix sum drops below 0.
• Off-by-one indexing: Column loops l=0 to cols-1, r=l to cols-1; row sums correct.
• Empty rectangle: If all negative, max sum is largest single element (not 0 unless specified).
• Integer overflow: With $100 \times 100 \times 1000 = 10^7$, use long long.
• 1D Kadane on non-contiguous: temp[i] must represent contiguous row sums.
• Symmetry optimization: No need (N=100), but row-major vs column-major irrelevant.

5. Time & Space Complexity

Time: $O(rows \times cols^2) = O(N^3)$. Outer loops: $O(cols^2)$, inner temp update + Kadane: $O(rows)$.

Space: $O(rows)$ for temp array (or $O(rows \times cols)$ for prefix sums). Optimal.

Proof sketch: $cols^2$ pairs × $rows$ for sum + $rows$ for Kadane = $O(N^3)$. No better exact algorithm known for dense matrices with negatives.