求一个m*n的整数矩阵的最大子矩阵和(子矩阵不能为空)。
比如在如下这个矩阵中:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
拥有最大和的子矩阵为:
9 2
-4 1
-1 8
其和为15。
#include <iostream> using namespace std; const int SIZE = 100; int matrix[SIZE+1][SIZE+1]; int rowsum[SIZE+1][SIZE+1]; //rowsum[i][j]记录第i行前j个数的和 int m, n, i, j, first, last, area, ans; int main() { cin>>m >>n; for(i=1; i<=m; i++) for(j=1; j<=n; j++) cin>> matrix[i][j]; ans = matrix____(1)_____; for(i=1; i<=m; i++) _____(2)______ for(i=1; i<=m; i++) for(j=1; j<=n; j++) rowsum[i][j] = ____(3)______ for(first = 1; first<=n; first++) for(last = first; last<=n; last++) { ____(4)_______ for(i=1; i<=m; i++) { area += ______(5)_______ if(area > ans) ans = area; if(area < 0) area = 0; } } cout<< ans <<endl; return 0; }