Max Sum of Rectangle - Problem Statement

Find maximum sum rectangle in a $2$D (two-dimensional) grid. This combines $1$D (one-dimensional) max subarray with column enumeration. Fix top and bottom rows. Compress columns to 1D array (sum of elements between rows). Apply Kadane's algorithm. With constraint that rectangle width $\leq k$: use sliding window maximum instead of Kadane. Time: $O(rows^2 \cdot cols)$

Time complexity: $O(n^2 \cdot m)$ for basic. With width constraint: $O(rows^2 \cdot cols)$ using monotonic queue for columns.

Space complexity: $O(n)$ for the prefix sums.