Problem overview
The method maxSum receives a grid of integers, a [][]int, and returns the largest sum among all its submatrices, which are rectangles of adjacent rows and columns. Values can be negative. In the example grid, the rectangle with rows 1 and 2 and columns 1 and 2 contains 10, 10, 9 and 9, and its sum, 38, is the answer.
Approach: fix two rows, then solve a 1D problem
Pick a top row x1 and a bottom row x2. Now add up each column between those rows. The result is a one-dimensional slice nums with one number per column. Any submatrix that spans exactly those rows corresponds to a contiguous run of nums, and its sum is the sum of that run. So the best submatrix for these two rows is the maximum subarray sum of nums, which a single pass can find.
That removes two of the four corner loops of the previous approach. The loops over x1 and x2 remain, giving O(m²) row pairs, and each costs O(n).
Building nums quickly needs column prefix sums: columnPartialSums[i][j] is the sum of column j from row 0 to row i. The column total between rows x1 and x2 is then columnPartialSums[x2][j] minus columnPartialSums[x1-1][j], where the second term is skipped when x1 is 0.
Step by step
- Store the sizes.
nis the number of rows andmthe number of columns, taken fromlen(grid)andlen(grid[0]). - Start
resultatgrid[0][0]. The answer can be negative, so 0 is not a safe start. A single cell is always a valid submatrix. - Declare
columnPartialSumsas a[][]intwithnrows. Each row starts asnil. - Fill it row by row. At the top of each iteration of the row loop, make row
ia slice ofmzeros, then loop over the columns. - Copy the cell:
columnPartialSums[i][j] = grid[i][j]. - Add what is above it when
i > 0: addcolumnPartialSums[i-1][j]. - Choose the top row
x1from 0 ton - 1. - Choose the bottom row
x2fromx1ton - 1. - Create
numsasmake([]int, m), one entry per column. - Loop over columns
y, settingnums[y]tocolumnPartialSums[x2][y]. - Remove the part above the top row when
x1 > 0, by subtractingcolumnPartialSums[x1-1][y]. - Solve the 1D problem by calling
this.maxSumSubarray(nums), then raiseresultif the returned sum is larger. - Return
result. - Write
maxSumSubarray: keep the best sum inresult(starting atnums[0]) and the sum of the current run inmaxSum(starting at 0). For each value, resetmaxSumto 0 if it is negative, add the value, and raiseresultifmaxSumis larger.
The solution in Go
type Solution struct{}
func (this Solution) maxSumSubarray(nums []int) int {
result := nums[0]
maxSum := 0
for _, val := range nums {
if maxSum < 0 {
maxSum = 0
}
maxSum += val
if maxSum > result {
result = maxSum
}
}
return result
}
func (this Solution) maxSum(grid [][]int) int {
n := len(grid)
m := len(grid[0])
result := grid[0][0]
columnPartialSums := make([][]int, n)
for i := 0; i < n; i++ {
columnPartialSums[i] = make([]int, m)
for j := 0; j < m; j++ {
columnPartialSums[i][j] = grid[i][j]
if i > 0 {
columnPartialSums[i][j] += columnPartialSums[i-1][j]
}
}
}
for x1 := 0; x1 < n; x1++ {
for x2 := x1; x2 < n; x2++ {
nums := make([]int, m)
for y := 0; y < m; y++ {
nums[y] = columnPartialSums[x2][y]
if x1 > 0 {
nums[y] -= columnPartialSums[x1-1][y]
}
}
sum := this.maxSumSubarray(nums)
if sum > result {
result = sum
}
}
}
return result
}
Go details:
for _, val := range numsyields an index and a copy of each value. The blank identifier_discards the index, which Go requires you to do because an unused variable is a compile error.- Methods calling methods.
this.maxSumSubarray(nums)calls another method of the same struct through the receiver. Go doesn't care about the order of declarations in a file, somaxSumSubarraymay sit above or belowmaxSum. - A fresh slice per row pair.
make([]int, m)inside the loop allocates a new slice each time. That costsO(n)memory per row pair, matching the time of filling it. +=and-=on slice elements work in place, with no temporary needed.
Kadane's algorithm in a nutshell
A run with a negative sum can only hurt any run that extends it, so the code throws it away and starts again at the next element. Because the reset happens before adding val, a slice such as [-3, -1, -2] still returns -1: each value starts a new run, and the best of those is the answer.
Complexity
Time: O(n² * m). With n rows and m columns there are about n²/2 row pairs, and each one costs O(m) to build nums and O(m) for the 1D pass. Building the column sums costs O(n * m). Choosing the shorter side as the rows lowers the cost when the grid is far from square.
Space: O(n * m). The column table has the grid's size, and nums adds O(m).
Edge cases and common mistakes
- All negative grid. For
[[-3, -1], [-2, -5]]the answer is -1. The code works becauseresultstarts from a real cell value and Kadane's pass starts fromnums[0]. - Starting a 1D result at 0. That would turn all-negative slices into 0, which isn't the sum of any non-empty subarray.
- Missing guard when
x1is 0.columnPartialSums[x1-1]would be index -1, which panics in Go. Theif x1 > 0check prevents it. - Single row or column. A one-row grid has one row pair, and
numsis the row itself. A one-column grid makes eachnumsa single value. - Unmade rows. Writing to a row of
columnPartialSumsbefore callingmakefor it panics, because the row isnil.
Testing
- The example grid gives
38. [[-3, -1], [-2, -5]]gives-1.[[5]]gives5.