363. Max Sum of Rectangle No Larger Than K
of No max sum than rectangle
2023-09-11 14:22:45 时间
Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.
Example:
Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of rectangle [[0, 1], [-2, 3]]
is 2,
and 2 is the max number no larger than k (k = 2).
Note:
- The rectangle inside the matrix must have an area > 0.
- What if the number of rows is much larger than the number of columns?
Approach #1:
class Solution { public: int maxSumSubmatrix(vector<vector<int>>& matrix, int k) { int row = matrix.size(); int col = matrix[0].size(); int ans = INT_MIN; for (int i = 0; i < col; ++i) { vector<int> temp(row, 0); for (int j = i; j < col; ++j) { for (int k = 0; k < row; ++k) temp[k] += matrix[k][j]; helper(temp, k, ans); } } return ans; } void helper(vector<int> temp, int k, int& ans) { int sum = 0; int cur_max = INT_MIN; set<int> s; s.insert(0); for (int i = 0; i < temp.size(); ++i) { sum += temp[i]; auto it = s.lower_bound(sum-k); if (it != s.end()) cur_max = max(cur_max, sum - *it); s.insert(sum); } ans = max(ans, cur_max); } };
Runtime: 172 ms, faster than 55.61% of C++ online submissions for Max Sum of Rectangle No Larger Than K.
here is a esay way to understand "largest sum of contiguous subarray No Larger than k"
private int maxSumSubArray(int[] a , int k){ int max = Integer.MIN_VALUE; for(int i=0;i<a.length;i++){ int tsum = 0; for(int j=i;j<a.length;j++){ tsum += a[j]; if(tsum <= k) max=Math.max(max,tsum); } } return max; }
相关文章
- Performance comparison for loops of List in java
- 04-树5 Root of AVL Tree (25分)
- [NPM] Run a set of similar npm scripts with a wildcard
- [AngularJS]8. No images, no gallery, ng-show
- 2. Using 'dp' instead of 'px' to set text size
- Unable to determine application id: com.android.tools.idea.run.ApkProvisionException: No outputs for the main artifact of variant: debug
- IPM: Technical model of IP right scope on Contract Item level
- No access for action Display of object type Product (PRODUCT)
- My year of 2017
- 【UVA 437】The Tower of Babylon(拓扑排序+DP,做法)
- 成功解决ValueError: Invalid classes inferred from unique values of `y`. Expected: [0 1], got [‘0‘ ‘1‘]
- 成功解决TypeError: object of type ‘int‘ has no len()
- 成功解决Python中出现的TypeError: object of type 'zip' has no len()
- Could not autowire. No beans of ‘GdjfConfirmSpotLandMapper‘ type found.
- 编写高质量JavaScript代码绳之以法(The Essentials of Writing High Quality JavaScript)翻译
- Analysis, visualization, and integration of spatial datasets with Seurat空间转录组空转
- ural 1932 The Secret of Identifier (容斥原理)
- IntelliJ Idea解决Could not autowire. No beans of 'xxxx' type found的错误提示
- e581. Animating an Array of Images in an Application
- springboot出现错误:No qualifying bean of type ’xxx‘ available
- 解决Mysql报错:This function has none of DETERMINISTIC, NO SQL, or READS SQL DATA in its de ————————————