Problem overview
The method maxSum receives a rectangular grid of integers as a number[][]. It returns the largest sum over all submatrices, where a submatrix is a rectangle of adjacent rows and columns with at least one cell.
In the example grid
[ 1, -9, -10, 1]
[-1, 10, 10, 1]
[ 0, 9, 9, -9]
[-1, -1, -1, -1]
the best rectangle is [[10, 10], [9, 9]], with sum 38.
Approach: fix two rows, then solve a 1D problem
Choose a top row x1 and a bottom row x2. Every rectangle between those two rows spans all the rows from x1 to x2 and some run of consecutive columns. Now squash the rows: for each column, add up its cells from row x1 to row x2. That gives one array of column sums, and the sum of a rectangle between those rows and columns a..b is exactly the sum of the squashed array over a..b.
So the best rectangle between rows x1 and x2 is the maximum sum subarray of the squashed array. That is the problem solved earlier in this chapter, and it takes one linear pass. Trying all pairs of rows covers every rectangle.
The squashed array needs to be cheap to build. A table of column prefix sums does it: columnPartialSums[i][j] holds the sum of column j from row 0 down to row i. The cells of column j between rows x1 and x2 then sum to columnPartialSums[x2][j] minus columnPartialSums[x1 - 1][j], where the subtraction is skipped when x1 is 0.
On the example, take rows 1 and 2. The column sums are -1 + 0 = -1, 10 + 9 = 19, 10 + 9 = 19 and 1 - 9 = -8. The best subarray of [-1, 19, 19, -8] is [19, 19], which is 38.
Step by step
- Store the sizes.
nis the number of rows (grid.length) andmthe number of columns (grid[0].length).resultstarts atgrid[0][0], because a single cell is a submatrix and the answer can be negative. - Create
columnPartialSums: an array ofnrows, each a new array ofmzeros. - Fill it. Loop over every cell
(i, j). Set the entry togrid[i][j]and, wheniis above zero, add the entry directly above it. Row 0 has nothing above it. - Choose the top row
x1and the bottom rowx2, withx2starting atx1. - Build the squashed array
numsof lengthm. For each columny, setnums[y]tocolumnPartialSums[x2][y], and whenx1is above zero, subtractcolumnPartialSums[x1 - 1][y]. This leaves only rowsx1tox2. - Solve the 1D problem by calling
this.maxSumSubarray(nums)and updateresultwithMath.max. - Return
result. - Write
maxSumSubarray. It keeps the best sum inresult, starting atnums[0], and the best sum of a run that ends at the current element inmaxSum, starting at 0. For each elementval,maxSumbecomesval + Math.max(maxSum, 0): a run with a negative sum is dropped, and the new run starts atval. Thenresulttakes the larger of itself andmaxSum.
The solution in TypeScript
class Solution {
maxSumSubarray(nums: number[]): number {
let result = nums[0];
let maxSum = 0;
for (const val of nums) {
maxSum = val + Math.max(maxSum, 0);
result = Math.max(result, maxSum);
}
return result;
}
maxSum(grid: number[][]): number {
const n = grid.length;
const m = grid[0].length;
let result = grid[0][0];
const columnPartialSums: number[][] = [];
for (let i = 0; i < n; ++i) {
columnPartialSums.push(new Array(m).fill(0));
}
for (let i = 0; i < n; ++i) {
for (let j = 0; j < m; ++j) {
columnPartialSums[i][j] = grid[i][j];
if (i > 0) {
columnPartialSums[i][j] += columnPartialSums[i - 1][j];
}
}
}
for (let x1 = 0; x1 < n; ++x1) {
for (let x2 = x1; x2 < n; ++x2) {
const nums: number[] = new Array(m);
for (let y = 0; y < m; ++y) {
nums[y] = columnPartialSums[x2][y];
if (x1 > 0) {
nums[y] -= columnPartialSums[x1 - 1][y];
}
}
const sum = this.maxSumSubarray(nums);
result = Math.max(result, sum);
}
}
return result;
}
}
Some TypeScript details:
constarrays can change.columnPartialSumsandnumsareconst, which only stops you from pointing the name at a different array. Pushing rows and assigning cells is fine.- Allocating without filling.
new Array(m)creates an array of lengthmwith empty slots. That is enough fornums, because the next loop assigns every index before anything reads it. Reading a never-assigned slot would giveundefined. - Compound assignment.
nums[y] -= columnPartialSums[x1 - 1][y]meansnums[y] = nums[y] - columnPartialSums[x1 - 1][y]. - Methods reach each other through
this.maxSumcalls its sibling asthis.maxSumSubarray(nums). The call works because it is made as a method call on the object, sothisis the instance. - Annotations are erased.
const nums: number[]is checked by the compiler only.
Complexity
Let the grid have n rows and m columns.
Time: O(n² * m). Building the column table costs O(n * m). There are about n² / 2 pairs of rows, and each pair costs O(m) to build nums and O(m) for the 1D pass. This beats the earlier approach that tried every pair of corners, which was O(n² * m²). If the grid has more rows than columns, you can transpose it first so the pair loop runs over the shorter side.
Space: O(n * m). The column table has the grid's shape. The array nums and the variables in the 1D pass add only O(m).
Edge cases and common mistakes
- All negative. For
[[-3, -1], [-2, -5]]the answer is-1. This works because bothresultvariables start from a real cell or element, not from 0. - Single row.
[[1, 2, 3]]gives6. The pair loop has onlyx1 = x2 = 0, and the problem is exactly the 1D one. - Single column.
[[1], [-5], [4]]gives4. Eachnumshas one element. - Forgetting to subtract above the top row. Without the
x1 > 0subtraction, every rectangle would be counted as if it started at row 0. - Starting the 1D pass at 0. If
resultinmaxSumSubarraystarted at 0, any row pair with all negative column sums would report 0, which is not a real submatrix sum. - Mixing up the sizes. The grid has
nrows andmcolumns here. Usingnas the column count in theyloop reads past the row's end for a non-square grid.
Testing
- The grid from the example gives
38. [[-3, -1], [-2, -5]]gives-1.[[1, 2, 3]]gives6.[[1], [-5], [4]]gives4.[[2, -1], [-1, 2]]gives2.