输入一个矩阵,找其中子矩阵元素和最大的子矩阵的C++代码实现
时间: 2023-11-30 19:05:16 浏览: 51
以下是一个基于动态规划的实现:
```c++
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
int maxSubmatrixSum(vector<vector<int>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
vector<vector<int>> dp(rows, vector<int>(cols)); // dp[i][j]表示以matrix[i][j]为右下角的子矩阵的元素和最大值
int maxSum = numeric_limits<int>::min(); // 最大元素和
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (i == 0 && j == 0) { // 初始化左上角的元素
dp[i][j] = matrix[i][j];
}
else if (i == 0) { // 第一行的元素
dp[i][j] = dp[i][j-1] + matrix[i][j];
}
else if (j == 0) { // 第一列的元素
dp[i][j] = dp[i-1][j] + matrix[i][j];
}
else { // 其他位置的元素
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i][j];
}
maxSum = max(maxSum, dp[i][j]); // 更新最大元素和
}
}
return maxSum;
}
int main() {
vector<vector<int>> matrix = {{1, 2, -1, -4, -20},
{-8, -3, 4, 2, 1},
{3, 8, 10, 1, 3},
{-4, -1, 1, 7, -6}};
int maxSum = maxSubmatrixSum(matrix);
cout << "Max submatrix sum: " << maxSum << endl;
return 0;
}
```
输入矩阵为:
```
1 2 -1 -4 -20
-8 -3 4 2 1
3 8 10 1 3
-4 -1 1 7 -6
```
输出结果为:
```
Max submatrix sum: 29
```
其中元素和最大的子矩阵为:
```
4 2 1
10 1 3
1 7 -6
```