题目传送门： 题目链接
题目描述：
| 一个M*N的矩阵，找到此矩阵的一个子矩阵，并且这个子矩阵的元素的和是最大的，输出这个最大的值。 例如：3*3的矩阵：
-1 3 -1 2 -1 3 -3 1 2
和最大的子矩阵是：
3 -1 -1 3 1 2
Input Output Input示例 Output示例 |
解题思路：
LL a[N][N]; // a[i][j] 代表的第 i 行前j个数的和
a[i][j1] - a[i][j2] 代表的是 第i行 ，j1+1 到 j2 的连续字段和，例: a[1][3] - a[1][1] = a[1][2] + a[1][3]，这种连续字段和一共 (m+1)*m/2 种。
然后将这些连续字段和看成一个元素，从 第1行 到 第n行 求最大连续字段和。
从所有的最大连续字段和中求得 最大值 就是 最大子矩阵和。
时间复杂度： m* (m+1)*m/2 空间复杂度：n^2
参考代码：
#include <iostream>
#include <cstring>using namespace std;typedef long long LL;
const int N = 510;// a[i][j] 代表的第 i 行前j个数的和
LL a[N][N]; int main()
{int n, m;cin >> m >> n;// 初始化memset(a, 0, sizeof(a)); for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {cin >> a[i][j];a[i][j] = a[i][j]+a[i][j-1];}}// ans 为最大子矩阵和int ans = a[1][1];for(int i=0; i<m; i++) {for(int j=i+1; j<=m; j++) {// i到j 代表的是 每行 i+1 到 j 的连续字段和，这种连续字段和一共 (m+1)*m/2 种。int temp = 0;// 然后将这些 连续字段和 (a[k][j]-a[k][i) 看成一个元素，从 第1行 到 第n行 求最大连续字段和;// 从所有的最大连续字段和中求得 最大值 就是 最大子矩阵和。 for(int k=1; k<=n; k++) { temp += a[k][j]-a[k][i];if(temp > ans) {ans = temp;}if(temp < 0) {temp = 0;}}}}cout << ans << endl;return 0;
}