DSA Tracker

Visualize

Maximum Sum Submatrix

Compress rows between a top/bottom boundary into one array, then run Kadane's algorithm

time O(R^2 * C)space O(C)

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.

Details

Animated on: Given a 2D matrix of integers, find the maximum sum of any rectangular submatrix within it.

Problem:Maximum Sum SubmatrixHard

Compress rows between a top/bottom boundary into one array, then run Kadane's algorithm

step 1 / 10

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.

Pseudocode
1FUNCTION maxSumRectangle(matrix):
2  best <- -INFINITY
3  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

Every step in words

Show all 10 steps
  1. 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.
  2. Fix the top boundary at row 0. Reset the column-sum row Σ to all zeros — it will hold the sum of every row from 0 down to the current bottom boundary.
  3. Row 0 added to Σ gives [1, 2, -1, -4, -20]. Kadane's best run in Σ is columns 0..1 summing to 3 — the best rectangle seen so far (rows 0..0), beating the previous best.
  4. Row 1 added to Σ gives [-7, -1, 3, -2, -19]. Kadane's best run in Σ is columns 2..2 summing to 3 — not enough to beat the current best of 3.
  5. Row 2 added to Σ gives [-4, 7, 13, -1, -16]. Kadane's best run in Σ is columns 1..2 summing to 20 — the best rectangle seen so far (rows 0..2), beating the previous best.
  6. Row 3 added to Σ gives [-8, 6, 14, 6, -22]. Kadane's best run in Σ is columns 1..3 summing to 26 — the best rectangle seen so far (rows 0..3), beating the previous best.
  7. Fix the top boundary at row 1. Reset the column-sum row Σ to all zeros — it will hold the sum of every row from 1 down to the current bottom boundary.
  8. Row 1 added to Σ gives [-8, -3, 4, 2, 1]. Kadane's best run in Σ is columns 2..4 summing to 7 — not enough to beat the current best of 26.
  9. Row 3 added to Σ gives [-9, 4, 15, 10, -2]. Kadane's best run in Σ is columns 1..3 summing to 29 — the best rectangle seen so far (rows 1..3), beating the previous best.
  10. No later (r1, r2) band beats it: the maximum sum rectangle is rows 1..3, columns 1..3, summing to 29.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Maximum Sum Submatrix in the editorAll Dynamic Programming problemsBack to roadmap