資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中不大於K的矩形最大和
假設我們有一個二維矩陣和一個整數k。我們必須找到矩陣中一個矩形的最大和，使其和不大於k。如果輸入如下：
| 1 | 0 | 1 |
| 0 | -3 | 2 |
並且k = 3，則輸出將為3，因為標記矩形的和為3。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式`maxSumSubmatrix()`，它將接收一個二維陣列`matrix`和`k`作為引數。
- n := 行數，m := 列數
- ans := -inf
- for l := 0 to m-1:
- 定義一個大小為n的陣列`rowSum`
- for r := l to m-1:
- for i := 0 to n-1:
- rowSum[i] := rowSum[i] + matrix[i][r]
- 定義一個集合s
- 將0插入s
- currSum := 0
- for i := 0 to n-1:
- currSum := currSum + rowSum[i]
- it := 集合s中不大於currSum – k的第一個元素
- if it != s的最後一個元素:
- ans := max(ans, (currSum - it))
- 將currSum插入s
- for i := 0 to n-1:
- 返回ans
讓我們看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
int m = matrix[0].size();
int ans = INT_MIN;
for(int l = 0; l < m; l++){
vector <int> rowSum(n);
for(int r = l; r < m; r++){
for(int i = 0; i < n; i++)rowSum[i] += matrix[i][r];
set < int > s;
s.insert(0);
int currSum = 0;
for(int i = 0; i < n; i++){
currSum += rowSum[i];
set <int> :: iterator it = s.lower_bound(currSum - k);
if(it != s.end()){
ans = max(ans, (currSum - *it));
}
s.insert(currSum);
}
}
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,0,1},{0,-3,2}};
cout << (ob.maxSumSubmatrix(v, 3));
}輸入
[{1,0,1},{0,-3,2}]
3輸出
3
更新於：2020年6月1日
瀏覽量：108
廣告