Problem overview
The method maxSum receives a grid of integers and returns the largest sum of any submatrix: a rectangle made of consecutive rows and consecutive columns. The numbers can be negative, so the whole grid is not always the best choice.
For the grid
1 -9 -10 1
-1 10 10 1
0 9 9 -9
-1 -1 -1 -1the answer is 38, from the block [[10, 10], [9, 9]].
In this lesson's code, n is the number of rows and m is the number of columns.
Approach: fix two rows, turn the rest into a 1D problem
Pick a top row x1 and a bottom row x2. Any rectangle between those two rows takes all the rows from x1 to x2 and a stretch of consecutive columns. Add up each column over just those rows, and you get one number per column: an array of m values. A rectangle between the two rows is then a contiguous subarray of that array, and its sum is the sum of the subarray.
So for each pair of rows, the question becomes: what is the largest sum of a contiguous subarray of this array? That is the Maximum Sum Subarray problem, which Kadane's algorithm solves in O(m).
Building the column sums for each pair of rows by adding up the rows would be slow. Instead, precompute columnPartialSums[i][j]: the sum of column j from row 0 down to row i. Then the sum of column y between rows x1 and x2 is columnPartialSums[x2][y] minus columnPartialSums[x1 - 1][y], the part above row x1, which only exists when x1 > 0.
In the example, take x1 = 1 and x2 = 2. The column sums over rows 1 and 2 are [-1, 19, 19, -8]. The best subarray of that is 19 + 19 = 38, which is the answer. The other row pairs give smaller values.
Step by step
- Store the sizes in
n(rows) andm(columns), both aslet, since they never change. Then createresultas avar, starting fromgrid[0][0]. A single cell is a submatrix, so this works even if every number is negative. Starting at 0 would not. - Create
columnPartialSums, a[[Int]]ofnrows ofmzeros, usingrepeating:count:at both levels. - Visit every cell with nested loops:
iover the rows,jover the columns. - Copy the cell into
columnPartialSums[i][j]. - Add the cell above when
i > 0, so each entry includes everything above it in the same column. - Choose the top row
x1with a loop over all rows. - Choose the bottom row
x2fromx1to the last row. The bottom cannot be above the top. - Create
nums, an array ofmzeros, to hold the column sums between those two rows. - Loop over each column
y. - Set
nums[y]to the column's sum from row 0 to rowx2. - Subtract the part above when
x1 > 0: removecolumnPartialSums[x1 - 1][y]. What is left is only rowsx1tox2. - Call
maxSumSubarray(nums)to get the best contiguous sum, keep it in a constant calledsum, and updateresultwithmax. - Return
resultafter the loops. - Write
maxSumSubarrayas the 1D solution:resultstarts atnums[0], a runningmaxSumstarts at 0, and for eachval,maxSum = val + max(maxSum, 0)andresult = max(result, maxSum). A negative running sum can only make the next subarray smaller, so it is replaced by 0 beforevalis added.
The solution in Swift
class Solution {
func maxSumSubarray(_ nums: [Int]) -> Int {
var result = nums[0]
var maxSum = 0
for val in nums {
maxSum = val + max(maxSum, 0)
result = max(result, maxSum)
}
return result
}
func maxSum(_ grid: [[Int]]) -> Int {
let n = grid.count
let m = grid[0].count
var result = grid[0][0]
var columnPartialSums = [[Int]](repeating: [Int](repeating: 0, count: m), count: n)
for i in 0..<n {
for j in 0..<m {
columnPartialSums[i][j] = grid[i][j]
if i > 0 {
columnPartialSums[i][j] += columnPartialSums[i - 1][j]
}
}
}
for x1 in 0..<n {
for x2 in x1..<n {
var nums = [Int](repeating: 0, count: m)
for y in 0..<m {
nums[y] = columnPartialSums[x2][y]
if x1 > 0 {
nums[y] -= columnPartialSums[x1 - 1][y]
}
}
let sum = maxSumSubarray(nums)
result = max(result, sum)
}
}
return result
}
}
The Swift details worth knowing:
- Two methods, one class.
maxSumcallsmaxSumSubarrayby its plain name. Inside a method, Swift looks the name up onself, so no prefix is needed, and the order in which the methods are written does not matter. - The same name at two levels. Both
maxSumSubarrayandmaxSumuse local variables calledresult. Each belongs to its own function and they do not interfere. InsidemaxSumSubarray,maxSumis a localInt, not the method. [[Int]](repeating:count:). The inner[Int](repeating: 0, count: m)is copied into each of thenrows. Arrays are value types, so the rows are independent and writing to one row does not change another.- Compound assignment.
+=and-=work directly on an element reached through two subscripts, likecolumnPartialSums[i][j] += .... - A fresh
numseach time. Declaring it withvarinside the loops makes a new array for every pair of rows. Its cells are all rewritten before use. - Empty input crashes.
grid[0]andnums[0]stop the program on an empty array. The lesson's tests use non-empty grids.
Complexity
Time: O(n² * m). There are about n² / 2 pairs of rows. For each pair, building nums costs O(m) and so does Kadane's algorithm. The prefix table costs O(n * m), which is smaller. Compared with enumerating all four corners, which takes O(n² * m²), this saves a whole factor of m.
Space: O(n * m). The table columnPartialSums has as many cells as the grid. The array nums adds only O(m).
Edge cases and common mistakes
- All negative numbers. For
[[-3, -1], [-2, -5]]the answer is-1, the best single cell. Bothresultvariables start from an actual element, so they are never stuck at 0. - A single row. With
[[1, 2, 3]], the only pair of rows isx1 = x2 = 0. The result is 6. - A single column.
[[1], [-2], [3]]gives 3. Eachnumshas one element. - Forgetting the subtraction when
x1 > 0. Without it,numswould hold the sums from row 0 down tox2, and the rows abovex1would count too. - Reading
columnPartialSums[x1 - 1]whenx1is 0. That index is -1 and crashes the program, which is what theif x1 > 0guard prevents. - Starting the inner search at row 0. The bottom row must run from
x1, otherwise the code would try rectangles with the bottom above the top.
Testing
- The grid from the example gives
38. [[-3, -1], [-2, -5]]gives-1.[[7]]gives7.[[1, 2, 3]]gives6.[[1], [-2], [3]]gives3.
