Problem overview
The method maxSum receives an Array[Array[Int]] called grid with n rows and m columns of integers, positive, negative or zero. It returns the largest sum of any rectangular block of cells, where a single cell is a valid block.
In the example grid
[ 1, -9, -10, 1]
[-1, 10, 10, 1]
[ 0, 9, 9, -9]
[-1, -1, -1, -1]
the best block is [[10, 10], [9, 9]], with sum 38.
Approach: fix the rows, then solve a 1D problem
Fix a top row x1 and a bottom row x2. A submatrix between those two rows is a run of consecutive columns, and its sum is the sum of the column totals over that run, where each column total adds the cells of that column from row x1 to row x2.
So once the column totals are in an array nums of length m, the best submatrix between the two rows is the best continuous subarray of nums. That is the Maximum Sum Subarray problem, which Kadane's algorithm solves in O(m). The answer is the best result over all pairs of rows.
The column totals are cheap if column prefix sums are prepared first. Entry columnPartialSums(i)(j) holds the sum of column j from row 0 down to row i. The total of column y between rows x1 and x2 is columnPartialSums(x2)(y), minus columnPartialSums(x1 - 1)(y) when x1 is greater than 0.
On the example, take x1 = 1 and x2 = 2. The column totals are [-1, 19, 19, -8]. The best run in that array is the middle two entries, with sum 38, which is the answer.
There are about n^2 / 2 pairs of rows, and each needs O(m) work to build nums and O(m) more for Kadane. That gives O(n^2 * m), better than the O(n^2 * m^2) of trying every pair of corners.
Step by step
- Store the sizes. Declare
nasgrid.lengthandmasgrid(0).length, both withval. - Create
resultas avarholdinggrid(0)(0). A single cell is a real submatrix, so this works even if every number is negative. Starting at 0 would be wrong. - Create
columnPartialSumsas avalwith a nestedArray.fill:nrows ofmzeros each. - Visit every cell with
iover the rows andjover the columns. - Copy the cell: set
columnPartialSums(i)(j)togrid(i)(j). - Add what is above it. If
i > 0, addcolumnPartialSums(i - 1)(j). Row 0 has nothing above it. - Choose the top row with
x1from 0 untiln. - Choose the bottom row with
x2fromx1untiln. It can't be above the top row. - Create
numsas aval, anArray.fill(m)(0), for the column totals between the two rows. - Loop
yover the columns, and setnums(y)tocolumnPartialSums(x2)(y). - Remove the part above the top row. If
x1 > 0, subtractcolumnPartialSums(x1 - 1)(y)fromnums(y). - Solve the 1D problem. Call
maxSumSubarray(nums), store it in avalcalledsum, and updateresultwithmath.max(result, sum). - End
maxSumwithresultas its last expression. - Write
maxSumSubarrayabove it. It is Kadane's algorithm:resultstarts atnums(0)andmaxSumstarts at 0. For eachvalue,maxSumbecomesvalue + math.max(maxSum, 0)andresultbecomes the larger of itself andmaxSum.
The solution in Scala
class Solution {
def maxSumSubarray(nums: Array[Int]): Int = {
var result = nums(0)
var maxSum = 0
for (value <- nums) {
maxSum = value + math.max(maxSum, 0)
result = math.max(result, maxSum)
}
result
}
def maxSum(grid: Array[Array[Int]]): Int = {
val n = grid.length
val m = grid(0).length
var result = grid(0)(0)
val columnPartialSums = Array.fill(n)(Array.fill(m)(0))
for (i <- 0 until n) {
for (j <- 0 until m) {
columnPartialSums(i)(j) = grid(i)(j)
if (i > 0) {
columnPartialSums(i)(j) += columnPartialSums(i - 1)(j)
}
}
}
for (x1 <- 0 until n) {
for (x2 <- x1 until n) {
val nums = Array.fill(m)(0)
for (y <- 0 until m) {
nums(y) = columnPartialSums(x2)(y)
if (x1 > 0) {
nums(y) -= columnPartialSums(x1 - 1)(y)
}
}
val sum = maxSumSubarray(nums)
result = math.max(result, sum)
}
}
result
}
}
The Scala details worth knowing:
- Two methods in one class.
maxSumcallsmaxSumSubarrayby its plain name. Methods of the same class can call each other in any order, so the helper doesn't have to be defined first. - Compound assignment on an array element.
columnPartialSums(i)(j) += ...andnums(y) -= ...read the element, change it and write it back. The arrays are mutable even though the names arevals. - A fresh
numsfor each pair of rows. It is declared inside the loop body, so every pair starts with its own zeroed array. The helper never changes it. - Separate rows from
Array.fill.Array.fill(n)(Array.fill(m)(0))builds a new inner array for each row, so the rows don't share cells. - The variable
resultappears twice, once in each method. Each is a separate local variable.
Complexity
Time: O(n^2 * m). Building the column prefix sums takes O(n * m). There are about n^2 / 2 pairs of rows, and for each pair both the loop over the columns and Kadane's algorithm take O(m).
Space: O(n * m). The prefix table has as many entries as the grid. Each nums array has m entries and is dropped after use.
Edge cases and common mistakes
- All numbers negative. For
[[-3, -1], [-2, -4]]the answer is -1. Bothresultvariables start from a real element, so negative answers work. - One cell.
[[5]]gives 5. - All numbers positive.
[[1, 2], [3, 4]]gives 10, the whole grid, from the pair of rows 0 and 1. - Forgetting the subtraction when
x1 > 0. The column totals would then include every row from the top of the grid, not only the rows fromx1tox2. - Starting
x2at 0. That would let the bottom row sit above the top row, and subtracting the prefix would give wrong totals. - Starting Kadane's
maxSumatnums(0). The recurrence expects the sum of the run before the first element to be 0. Starting fromnums(0)would add the first element twice.
Testing
- The example grid above gives
38. [[-3, -1], [-2, -4]]gives-1.[[5]]gives5.[[1, 2], [3, 4]]gives10.
