Funcia
Lv.3dpgridkadaneprefix-sum

Maximum-Sum Submatrix

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

A field of R rows and C columns is divided into cells; grid[i][j] is the profit of the cell in row i, column j (negative means a loss). Choose one axis-aligned rectangle of cells (at least one cell) and collect the profit of every cell inside it. Return the maximum total profit.

Examples

gridresult
[[1, -2, 3], [-4, 5, 6], [7, -8, 9]]18
[[-5, -2], [-3, -9]]-2
[[2, 3, -100, 4]]5

Example 1 — The whole right column: 3 + 6 + 9 = 18.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(grid: int[][]) → long

Constraints

  • 1≤R=1 \le R = grid.length ≤300\le 300, 1≤C=1 \le C = grid[i].length ≤300\le 300 (all rows have the same length)
  • −106≤-10^6 \le grid[i][j] ≤106\le 10^6
  • The answer may exceed 32 bits.

Expected complexity

Time
O(R^2 * C)
Space
O(C)

Examples

gridExpected
[[1,-2,3],[-4,5,6],[7,-8,9]]18
[[-5,-2],[-3,-9]]-2
[[2,3,-100,4]]5

Hint

Hint

Fix the top and bottom rows; summing each column over that band gives an array col whose maximum subarray sum (Kadane, O(C)O(C)) is the best rectangle for the band. Extending bottom adds one row to col, so the total is O(R2C)O(R^2 C). Use 64-bit sums. Checking every rectangle with 2D prefix sums is O(R2C2)O(R^2 C^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.133490 msderived
Java 251034 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.