Maximum sum rectangle bounded
Given an m x n integer matrix and an integer k, find the maximum sum of a rectangular submatrix such that the sum is no larger than k. It is guaranteed that at least one such submatrix exists. Return that maximum sum (which may be negative).
Implement
max_sum_submatrix(matrix: list[list[int]], k: int) → intExamples
in
[[[1,0,1],[0,-2,3]],2]out2What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 45 min
solution.py
InputExpectedGot
[[[1,0,1],[0,-2,3]],2]2not run yetsample