363. Max Sum of Rectangle No Larger Than K

Given an `m x n` matrix of integers and an integer `k`, find the max-sum submatrix such that its sum ≤ k. (Use prefix-sum plus either balanced tree or 1D max-subarray approach per row-pair.)

Input Format

2D list and k.

Output Format

Integer max sum.

Constraints

  • m,n ≤ 100; -100 ≤ values ≤ 100.

Examples

Example 1:

Input:

matrix = [[1,0,1],[0,-2,3]]
k = 2

Output:

2

Explanation:

The submatrix [[0,1],[-2,3]] has sum 2 which is max ≤ 2.

Loading...
363. Max Sum of Rectangle No Larger Than K