Richest Plot Under the Cap

Hard

A field is divided into cells, and field[i][j] is the profit of a cell (it can be negative when a cell costs money to work). Choose one plot, a rectangle of cells aligned with the grid, whose total profit does not exceed cap. Return the largest total profit such a plot can have. At least one valid plot is guaranteed to exist. Follow-up: how would you change the approach if there are far more rows than columns?

Example 1

field=[[3, -1], [2, 4]], cap=5 → 5

The left column gives 3 + 2 = 5, exactly the cap. Rectangles with larger sums (such as the bottom row, 6) are not allowed.

Example 2

field=[[-2, 7, 1]], cap=0 → -2

The only rectangle whose sum is at most 0 is the single cell -2.

Constraints

m == len(field), n == len(field[i])
1 ≤ m, n ≤ 150
-100 ≤ field[i][j] ≤ 100
-10⁵ ≤ cap ≤ 10⁵
Some plot has a total of at most cap

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Matrix Ordered Set Prefix Sum

Similar problems

Flowers in Bloom on Visit Day Hard Climbing Along Rows and Columns Hard Largest Light Square Medium Frame Around an Ink Blot Hard Smaller Values to the Right Hard

Input

field=[[3, -1], [2, 4]], cap=5

Expected

Run checks the first 3 tests in your browser. Submit checks all 200 tests on the server, hidden ones included.