问题 1156 --最大子矩阵和(完善程序)

1156: 最大子矩阵和(完善程序)★★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 1525  解决: 974
[提交][状态][命题人:]

题目描述

求一个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;
}


输入

输入的第1行给出两个整数m和n(0<n<=100)。后面跟有m行数据,每行含有n个整数,每个整数间使用空格分隔。

输出

最大子矩阵和。

样例输入
Copy
4 4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
样例输出
Copy
15

提示

普及组+提高组

来源

[提交][状态]