Hard Problemsgridoptimization

Maximum sum rectangle

Given a 2D matrix of integers that may be positive or negative, find the axis-aligned rectangular submatrix whose entries add up to the largest possible total.

Note. This is typically solved by collapsing pairs of rows into a running column sum and applying Kadane's algorithm to it, rather than by one recurrence over a table.

Do this lesson first: house robber

Example input

the 2 by 12 matrix [[-3, -4, 4, -6, -4, 1, -6, 6, 0, 5, -2, 2], [-4, -2, 1, -2, -6, 6, -5, 5, 3, 2, 5, -5]]

Expected output

24, from rows 0 to 1 and columns 7 to 10

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

TWO KINDS OF ROW, and reading the table means knowing which one you are standing on. A K cell is the one that holds a subproblem answer: K[t-b][j] is THE LARGEST RECTANGLE SUM WHOSE ROW BAND IS EXACTLY ROWS t TO b AND WHOSE RIGHT EDGE IS EXACTLY COLUMN j. Both exactlys are doing work. The band is pinned, so a rectangle using only row 0 is not a candidate for the band 0-1 cell even though it fits inside those rows; that rectangle has its own cell, in the band 0-0 rows. The right edge is pinned, so a rectangle stopping at column j - 1 is not a candidate for column j either. What is NOT pinned is the left edge, and that is the only freedom a K cell has: it ranges over every start column from 0 to j. A C cell is a different animal and is not a subproblem answer at all. C[t-b][j] is the total of column j over exactly rows t to b, which is arithmetic on the input rather than the answer to any question the statement asks. It exists because Kadane's scan needs one number per column, and collapsing the band is how a rectangle problem becomes a one-dimensional one. THE ANSWER IS THE LARGEST K CELL ANYWHERE IN THE TABLE, not a corner and not the end of a row, and that is structural rather than a quirk of this matrix: every rectangle in the matrix has exactly one row band and exactly one right edge, so it is counted at exactly one K cell, and the largest rectangle is therefore the largest K cell. No C cell can beat them, since K[t-b][0] equals C[t-b][0] and every later K cell is a max whose first candidate is its own C cell. WHICH CELL WINS MOVES, and the slider is there to show it. Across the eight column counts from 5 to 12 the answer cell is K[0-1] at columns 2, 5, 5, 7, 8, 9, 10 and 10, and the answer reads 5, 7, 7, 11, 14, 21, 24 and 24. maximum-square-submatrix-of-ones says the same thing about itself and for the same reason: when the answer is an argmax rather than a corner, the table has to be searched once it is full, and a page that always pointed at the same cell would be teaching a coincidence.

K[t-b][j] = max(C[t-b][j], K[t-b][j-1] + C[t-b][j]) for j > 0, where C[t-b][j] is column j totalled over rows t to b; and for the two-row band, C[0-1][j] = C[0-0][j] + C[1-1][j]

Stand at column j of one band and ask about the best rectangle whose right edge is column j. Its left edge is either column j itself, or something further left. If it is column j itself, the rectangle is that one column of the band and it is worth C[t-b][j]. If it is further left, then chopping column j off it leaves a rectangle in the same band ending at column j - 1, and the best such rectangle is exactly what K[t-b][j-1] holds, so the whole thing is worth K[t-b][j-1] + C[t-b][j]. Those two cases are exhaustive and the cell takes the larger. START FRESH OR EXTEND, and the C[t-b][j] term appears in both, which is what makes the decision so cheap to see: the two candidates differ by K[t-b][j-1] and nothing else. So a NEGATIVE RUNNING TOTAL IS ALWAYS WORTH DISCARDING, and that is a proof rather than an instinct. If K[t-b][j-1] is negative then K[t-b][j-1] + C[t-b][j] is smaller than C[t-b][j] whatever C[t-b][j] happens to be, so the fresh start wins by exactly the amount the carried prefix was under water. It has nothing to do with the sign of the current column. Column 6 of the two-row band is the case that makes this concrete and it points the other way: the column total is -11, which is as negative as anything on the table, and the cell still EXTENDS, because the 7 to its left is positive and 7 + -11 = -4 is better than -11. Column 7 restarts, on the same band, one column later, because the -4 it would carry is negative. The current column's sign never enters either decision. THE OTHER RECURRENCE ON THIS TABLE IS THE ROW COLLAPSE and it is not a decision at all. The column totals of the band rows 0 to 1 are the column totals of row 0 plus the column totals of row 1, added straight down, which is why the C row of the two-row band is computed here rather than handed over: the sum of a band is the sum of the bands it is made of, and the general form of that is C[t-b][j] = C[t-(b-1)][j] + matrix[b][j], one row added at a time.

TWO ROWS AND THREE CELLS ARE BASES, 27 of the 72 cells at the full 12 columns, and each of the two kinds is a base for a different reason. THE FIRST KIND IS THE TWO SINGLE-ROW C ROWS. The column totals of a band that is one row deep are that row of the matrix, unchanged: there is nothing to add up. So C[0-0] IS the matrix's first row and C[1-1] IS its second, and the whole input is visible on the table before a single cell is computed. THE SECOND KIND IS THE FIRST COLUMN OF EACH K ROW, three cells in all. Kadane genuinely starts there. The only rectangle in a band whose right edge is column 0 is column 0 itself, since there is nothing to its left to extend, so K[t-b][0] = C[t-b][0] with no decision to make and no cell to compare against. That is the same reason longest-increasing-subsequence declares dp[0] = 1 rather than computing it. WHAT IS NOT A BASE IS THE POINT OF THE PAGE. The C row of the two-row band, 12 of the 45 computed cells, is COMPUTED, from the two single-row C rows one column at a time. It would have been easy to hand that row over as data, since the matrix is right there, and the page would then have started from three collapsed bands and only ever shown Kadane. Computing it puts the row collapse the problem is named for inside the trace, with its own reads and its own gate, instead of in the setup. ORDER is row-major and it needs exactly two properties, both of which the layout was arranged to give it. A K cell at column j reads its own band's C cell in the row directly above and its own K cell one column to the left, so it needs the row above finished and the current row filled left to right. The C cell of the two-row band reads the two single-row C cells in the same column, which sit in table rows 0 and 2, so it needs the two single-row bands laid out FIRST. That is why the band order is 0-0, 1-1, 0-1 and not, say, 0-0, 0-1, 1-1: the enumeration order of the bands is free in the algorithm, and here it is spent on making the collapse a computed row.

Tabulation, one row-major sweep, 45 computed cells at 12 columns against 27 bases. THE ROW-BAND COLLAPSE IS THE WHOLE METHOD and it is worth stating in its general form, because the 2-row matrix on this page is small enough to hide it. A rectangle is fixed by four numbers, its top, bottom, left and right edge, and enumerating all four is O(rows^2 x cols^2) before you even add the entries up. Fix the top and bottom FIRST and something collapses: the band becomes a single strip of column totals, and the best rectangle inside a fixed band is the best contiguous run in that strip, which is Kadane in one pass. So the cost is one Kadane per band, and the number of bands is the number of ways to choose a top and a bottom with top no lower than bottom, which is m(m + 1) / 2 for an m-row matrix: 1 band at m = 1, 3 at m = 2, 6 at m = 3, 10 at m = 4. Total time O(m^2 x n) for an m by n matrix, and O(n) space is enough if you keep only the current band's totals and one running value, since a K cell reads its own band's column total and the running value one column to its left and nothing from any earlier band. THIS PAGE SHOWS THE WHOLE TABLE INSTEAD, and that is where its costs are, so here they are rather than buried. FIRST COST: the matrix has two rows because the table cannot afford three. Two table rows per band times m(m + 1) / 2 bands is m(m + 1) table rows, so m = 2 costs 6 and m = 3 would cost 12, against the 10-row bound the suite asserts. At m = 2 only ONE of the three bands, 0-1, is a genuine two-row band, so the collapse that the general method performs m(m + 1) / 2 - m times happens exactly once in this animation. The matrix was chosen so that that one band is where the answer lives at every slider size, which keeps the page honest but does not make the band count larger than it is. SECOND COST, and this one is a first for the catalog: THE ROWS OF THIS TABLE RUN TWO DIFFERENT RECURRENCES. A C row adds two cells with no comparison; a K row takes a max of two candidates. Which one applies is decided by the row you are on rather than by anything in the cell's own data, so `combine` branches on the row index. THAT IS MEASURABLE RATHER THAN A MATTER OF TASTE, and it was measured: `combine` reports an operator per cell, and driving every authored page at every one of its slider sizes and collecting the set of operators each page returns, this is the only page whose set has more than one member. Pages that branch heavily still report one: maximum-square-submatrix-of-ones branches on whether the matrix holds a 0 at that cell, water-overflow on how many parents a glass has, and in both the branches state the same recurrence and report the same operator. Rerun that sweep rather than trusting this paragraph; it will stop being true the first time another page mixes operators. THE READER PAYS FOR IT IN THE CODE PANEL, in THREE places rather than one, and the honest way to state the size of that is to count the steps that highlight the wrong line. A spec declares one line each for `init`, `base`, `read`, `write` and `done`, for the whole page. This page names line 7 for a base, which is right for the 24 C-row bases and wrong for the 3 K-row first cells; line 11 for a read and a write, which is right for the 33 K reads and the 33 K writes and wrong for the 12 C reads and the 12 C writes. So at 12 columns 27 of the 152 steps highlight a line that is not the one doing their work, a bit under a fifth. The split was chosen to make that number as small as it goes under a single line per kind: naming line 8 for the base instead, which is Kadane's own first column, would be right for 3 bases and wrong for 24 and would push the total to 48 of 152. RECOUNT rather than trusting those figures, which move with the column count: drive the spec, bucket every step by whether its cell sits in a C row or a K row, and compare each bucket against the line its kind names. The mismatch is not repaired anywhere, because repairing it means letting `codeLines` take a function of the cell, which is a change to a contract every page in the course shares.

Time O(m² × n) for an m by n matrix: m(m + 1) / 2 row bands, one O(n) Kadane pass each, which is 3 bands and 12 columns hereSpace O(m² × n) to show the whole table, reducible to O(n) with one array of column totals and one running value

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

TWO ROWS AND THREE CELLS ARE BASES, 27 of the 72 cells at the full 12 columns, and each of the two kinds is a base for a different reason. THE FIRST KIND IS THE TWO SINGLE-ROW C ROWS. The column totals of a band that is one row deep are that row of the matrix, unchanged: there is nothing to add up. So C[0-0] IS the matrix's first row and C[1-1] IS its second, and the whole input is visible on the table before a single cell is computed. THE SECOND KIND IS THE FIRST COLUMN OF EACH K ROW, three cells in all. Kadane genuinely starts there. The only rectangle in a band whose right edge is column 0 is column 0 itself, since there is nothing to its left to extend, so K[t-b][0] = C[t-b][0] with no decision to make and no cell to compare against. That is the same reason longest-increasing-subsequence declares dp[0] = 1 rather than computing it. WHAT IS NOT A BASE IS THE POINT OF THE PAGE. The C row of the two-row band, 12 of the 45 computed cells, is COMPUTED, from the two single-row C rows one column at a time. It would have been easy to hand that row over as data, since the matrix is right there, and the page would then have started from three collapsed bands and only ever shown Kadane. Computing it puts the row collapse the problem is named for inside the trace, with its own reads and its own gate, instead of in the setup. ORDER is row-major and it needs exactly two properties, both of which the layout was arranged to give it. A K cell at column j reads its own band's C cell in the row directly above and its own K cell one column to the left, so it needs the row above finished and the current row filled left to right. The C cell of the two-row band reads the two single-row C cells in the same column, which sit in table rows 0 and 2, so it needs the two single-row bands laid out FIRST. That is why the band order is 0-0, 1-1, 0-1 and not, say, 0-0, 0-1, 1-1: the enumeration order of the bands is free in the algorithm, and here it is spent on making the collapse a computed row.

row band t-b, then C for that band's column totals or K for the best rectangle in that band ending at this column

0

1

2

3

4

5

6

7

8

9

10

11

0-0 C

-3

-4

4

-6

-4

1

-6

6

0

5

-2

2

0-0 K

-3

-4

4

-2

-4

1

-5

6

11

9

11

1-1 C

-4

-2

1

-2

-6

6

-5

5

3

2

5

-5

1-1 K

-4

-2

1

-1

-6

6

1

6

9

11

16

11

0-1 C

-7

-6

5

-8

-10

7

-11

11

3

7

3

-3

0-1 K

-7

-6

5

-3

-10

7

-4

11

14

21

24

21

column j of the matrix, which is the RIGHT EDGE of every rectangle a K cell in this column is about

maximum-sum-rectangle.ts

1function maxSumRectangle(matrix) {
2 const rows = matrix.length, cols = matrix[0].length;
3 let best = -Infinity;
4 for (let top = 0; top < rows; top++) {
5 const colTotal = new Array(cols).fill(0);
6 for (let bottom = top; bottom < rows; bottom++) {
7 for (let j = 0; j < cols; j++) colTotal[j] += matrix[bottom][j];
8 let running = colTotal[0];
9 best = Math.max(best, running);
10 for (let j = 1; j < cols; j++) {
11 running = Math.max(colTotal[j], running + colTotal[j]);
12 best = Math.max(best, running);
13 }
14 }
15 }
16 return best;
17}

Base caseComputedBeing readAnswer

The code, the trap, the variations

maximum-sum-rectangle.ts

1function maxSumRectangle(matrix) {
2 const rows = matrix.length, cols = matrix[0].length;
3 let best = -Infinity;
4 for (let top = 0; top < rows; top++) {
5 const colTotal = new Array(cols).fill(0);
6 for (let bottom = top; bottom < rows; bottom++) {
7 for (let j = 0; j < cols; j++) colTotal[j] += matrix[bottom][j];
8 let running = colTotal[0];
9 best = Math.max(best, running);
10 for (let j = 1; j < cols; j++) {
11 running = Math.max(colTotal[j], running + colTotal[j]);
12 best = Math.max(best, running);
13 }
14 }
15 }
16 return best;
17}

Where people go wrong

Reading the end of the last K row as the answer. The answer is the largest K cell ANYWHERE, and on this table it is not the last one: at 12 columns K[0-1][11] holds 21 while the answer, 24, sits one column to its left. That is not a near miss engineered for the page either. The last cell of a K row is the best rectangle whose right edge is the last column, and there is no reason for the best rectangle in the matrix to end there; whenever the columns after the true right edge total negative, as column 11 totals -3 here, the last cell is strictly smaller. The same mistake in the code is initialising `best` after the loops instead of updating it inside them. THE SECOND MISTAKE IS SKIPPING THE SINGLE-ROW BANDS, and it is the one the picture encourages. The problem says rectangle, the method says collapse a band of rows, and it is easy to hear both as meaning the rectangle must be more than one row tall. It need not be: a one-row rectangle is a rectangle, and the bands with top equal to bottom are exactly the ones that find them. Drop them here and the answer on this matrix does not move, because the two-row band wins at every slider size, which is precisely why the failure is dangerous rather than obvious. Change the matrix and it bites, though it takes more than a single-row optimum to make it bite, and the near miss is worth seeing first. On [[1, -3, 4, 2, -1, 5], [-2, 6, -4, 3, 1, -3]] the best rectangle IS a single row, columns 2 to 5 of row 0 summing to 10, and a solver skipping the single-row bands still returns 10, because that 10 is TIED: columns 1 to 5 of both rows reach it too. A tie rescues the broken solver. On [[-5, 3, 1, -2, 6, -6], [-5, -4, 1, 1, -4, -1]] nothing rescues it. The best rectangle there is columns 1 to 4 of row 0, summing to 8, it is the unique rectangle reaching 8, and the best rectangle using both rows is only 3, so a solver that skipped the single-row bands returns 3 against a true 8. Check that by brute force over the four corners rather than taking it from here, and check the uniqueness too, since it is the half that makes the example work. THE THIRD IS SEEDING THE RUNNING TOTAL WITH ZERO, which is the same bug wearing a rectangle costume. Write `running = Math.max(0, running + colTotal[j])` and you have allowed the EMPTY rectangle, worth 0, as a candidate. On a matrix with a positive answer nothing goes wrong and the bug ships. On an all-negative matrix every answer comes back 0, which is not the sum of any rectangle at all. On this very matrix, take the leftmost 2 columns: every rectangle inside them is negative, the true answer is -2, the single cell in row 1 column 1, and the zero-seeded version returns 0. The slider starts at 5 columns so the page never shows that case; the bug is still there at 5 columns, waiting for a different matrix. THE FOURTH IS COLLAPSING THE BAND FROM SCRATCH FOR EVERY BAND, which costs correctness nothing and time a whole factor of m. Adding the band rows up afresh for each of the m(m + 1) / 2 bands is O(m) per column per band; carrying the previous band's totals and adding one matrix row is O(1). This table does the cheap version in plain sight: C[0-1] is C[0-0] plus C[1-1], read off the table, not re-added from the matrix.

Report the rectangle's four corners, not just its total.
The recurrence does not change and the fill order does not change. What changes is what a K cell remembers: alongside its value it carries the LEFT edge of the rectangle that achieved it, which is column j itself when the cell restarts and the previous cell's remembered left edge when it extends. The band supplies the top and bottom, the cell's own column supplies the right edge, so the argmax cell then names all four. At 12 columns the answer cell K[0-1][10] would carry left = 7, and rows 0 to 1, columns 7 to 10 is the rectangle. Note that ties become visible in a way the total hides: at 12 columns the best rectangle inside row 0 alone is 11 and TWO different rectangles reach it, columns 7 to 9 and columns 7 to 11, so a corner-reporting version has to say which one it means.
Allow the empty rectangle, so the answer can never be below 0.
One line, and it is the line the third pitfall warns about, so it is worth seeing it work correctly for once. Take the answer as max(0, largest K cell) at the END, rather than folding a 0 into the running total inside Kadane's step. The two agree on the ANSWER, and they agree for a reason rather than by luck: a Kadane scan that clamps its running value at 0 reports max(0, the largest rectangle sum), which is what max(0, largest K cell) reports too. Where they differ is what the CELLS mean. A clamped cell holds the best rectangle-or-nothing ending at that column, so it reads 0 wherever every rectangle ending there is negative, and the state paragraph on this page would stop describing it. On this matrix the distinction never reaches the answer at any slider position, since the answer is 5 or more at all eight; on the leftmost 2 columns the table's answer is -2 and the empty-rectangle answer is 0, and both are right answers to their own question.
Give the matrix more rows.
Nothing about the recurrence changes and everything about the size does. The band count goes as m(m + 1) / 2, so 3 rows give 6 bands and 4 give 10, and this table's two rows per band would need 12 and 20 table rows against a 10-row budget. That is the honest reason the matrix here is 2 rows deep. The general method does not care: it walks the bands top by top, keeping one array of column totals per top and adding one matrix row as the bottom descends, which is the same arithmetic as this page's computed C row generalised. Total time O(m² × n), and note which dimension is squared. For a tall thin matrix, transpose first: bands over the SHORT side and Kadane along the long one turns O(m² × n) into O(n² × m), which on a 1000 by 10 matrix is a factor of 100 either way round, since the two costs differ by m over n and not by its square.

Printing Matrix Chain Multiplication Stock Buy and Sell – At-Most k Times