Pattern visualizer
Maximum Sum Rectangle in 2D Matrix
A rectangle is defined by two row boundaries and two column boundaries. Fixing the row boundaries first turns the problem 1D: sum every row between them into a single column-sum array Σ, and now the best rectangle for THIS row band is just the best contiguous run in Σ — exactly what Kadane's algorithm finds in O(C). Trying all O(R^2) row-boundary pairs, each with an O(C) Kadane pass, beats checking every rectangle directly. Animated on: Given a 2D matrix of integers, find the maximum sum of any rectangular submatrix within it..
Compress rows between a top/bottom boundary into one array, then run Kadane's algorithm
matrix, with a running column-sum row (Σ) underneath
Trying every rectangle directly is O(R^2 * C^2). Instead, fix a top row r1 and a bottom row r2, compress every row between them into one column-sum row Σ, then find the best run in Σ with Kadane's algorithm — that run IS the best rectangle for this (r1, r2) band.
1FUNCTION maxSumRectangle(matrix):2 best <- -INFINITY3 FOR r1 FROM 0 TO ROWS(matrix) - 1:4 colSums <- ZEROS(COLS(matrix))5 FOR r2 FROM r1 TO ROWS(matrix) - 1:6 FOR c FROM 0 TO COLS(matrix) - 1:7 colSums[c] <- colSums[c] + matrix[r2][c]8 sum <- KADANE(colSums)9 best <- MAX(best, sum)10 RETURN best
← / → step · space play · Home restart