337. Maximum Sum Rectangle in a 2D Matrix

Given a matrix of integers (which may include negative numbers), find the maximum possible sum of the elements within any rectangular sub-matrix.

Input: The first line contains rows and cols. Each of the next rows lines contains cols space-separated integers (which may be negative) forming the matrix. Output: Print a single integer - the maximum sum obtainable from any rectangular sub-matrix.

1 <= rows, cols <= 200

Unlike the zero-sum variant, NEGATIVE numbers here mean the best 'rectangle' can legitimately be a SINGLE CELL if everything else would only make the sum worse - Kadane's algorithm naturally handles this correctly by allowing a fresh restart at any position.

Find the maximum possible sum of any rectangular sub-matrix, allowing negative numbers. Brute force: Check every possible rectangle directly (every pair of top-left and bottom-right corners) and sum its elements from scratch - this costs O(rows²*cols²) or worse, far too slow for rows,cols up to 200. Optimised: Reducing the 2D problem to a SEQUENCE of 1D 'maximum subarray sum' problems (one per pair of top/bottom rows, using Kadane's algorithm on the collapsed column sums) turns an expensive 2D search into O(rows²) independent, efficient O(cols) computations.

Precompute a 2D prefix-sum matrix in one O(rows*cols) pass, where each cell holds the sum of the sub-matrix from the origin to that cell. With this precomputed, the sum of ANY rectangle can then be looked up in O(1) using inclusion-exclusion on the four corners of the prefix-sum matrix. Still trying every pair of corners as in the brute-force approach, this removes the need to re-sum each rectangle's interior cells individually, replacing an O(rows*cols) per-rectangle cost with an O(1) lookup. Time: O(rows^2 * cols^2) Space: O(rows * cols)

Fix every pair of left and right column boundaries, and for each pair, collapse the matrix between those columns into a single 1D array by summing across columns for each row; then run Kadane's maximum-subarray algorithm on that 1D array to find the best contiguous run of rows in linear time. This reduces the 2D rectangle-sum problem to many 1D maximum-subarray problems, replacing the brute-force search over all four rectangle corners with a search over only column-pairs (or row-pairs, whichever dimension is smaller) combined with an efficient 1D scan, which is the standard optimal technique for this problem. Time: O(cols^2 * rows) Space: O(rows)

Consider every possible pair of top-left and bottom-right corners that defines a rectangular sub-matrix, and for each one, sum up all the elements inside it by iterating over every cell in that rectangle directly, keeping track of the best sum seen. This checks every possible rectangle exhaustively and is guaranteed correct, but recomputing each rectangle's sum from scratch by revisiting all of its cells makes it extremely slow for matrices up to 200x200. Time: O(rows^2 * cols^2 * rows * cols) Space: O(1)

1. Fix a pair of top and bottom rows, and COLLAPSE every column between them into a single running column-sum array. 2. The best rectangle using EXACTLY those top/bottom rows is then just the MAXIMUM-SUM CONTIGUOUS SUBARRAY (Kadane's algorithm) over that collapsed 1D array. 3. Try every pair of top and bottom rows (O(rows²) pairs) and take the best Kadane's result over all of them.

Time: O(rows² * cols) - O(rows²) pairs of rows, each requiring an O(cols) Kadane's pass on the collapsed array. Space: O(cols), for the collapsed column-sum array reused across row-pairs.

Test a matrix that is entirely negative (the best 'rectangle' is a single least-negative cell), a 1x1 matrix, and rows = cols = 200 (upper bound) for the O(rows^2 * cols) row-collapsing plus Kadane approach.

Be ready to connect this directly to 'Largest Rectangular Sub-Matrix Whose Sum Is 0' - both use the identical row-collapsing technique, just applying a different 1D algorithm afterward (Kadane's for maximum sum here, versus the zero-sum-subarray hashmap technique there).