最大和(最大子矩阵DP，注意全是负数的情况)

喜欢ヅ旅行 2022-08-02 05:57 127阅读 0赞

## 最大和 ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 5

描述

给定一个由整数组成二维矩阵（r\*c），现在需要找出它的一个子矩阵，使得这个子矩阵内的所有元素之和最大，并把这个子矩阵称为最大子矩阵。   
例子：  
0 -2 -7 0   
9 2 -6 2   
\-4 1 -4 1   
\-1 8 0 -2   
其最大子矩阵为：

9 2   
\-4 1   
\-1 8   
其元素总和为15。

输入

第一行输入一个整数n（0<n<=100）,表示有n组测试数据；  
每组测试数据：  
第一行有两个的整数r，c（0<r,c<=100），r、c分别代表矩阵的行和列；  
随后有r行，每行有c个整数；

输出

输出矩阵的最大子矩阵的元素之和。

样例输入

1
    4 4
    0 -2 -7 0 
    9 2 -6 2 
    -4 1 -4 1 
    -1 8 0 -2

样例输出

来源

[\[苗栋栋\]原创][Link 1]

上传者

[苗栋栋][Link 2]

**注意全是负数的情况就可以了**

#include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    int map[105][105];
    int maxs;
    int main()
    {
        //cout<<-0x3f3f3f3f<<endl;
        int n,i,j,v,k,sum,t,m;
        cin>>t;
        while(t--)
        {
            cin>>n>>m;
            memset(map,0,sizeof(map));
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=m;j++)
                {
                    cin>>v;
                    map[i][j]=map[i][j-1]+v;
                }
            }//这个的每一列的每一个数字是前面的数字之和！这样就确保了每一列是线性的！
            for(i=1,maxs=map[1][1];i<=m;i++)
            {
                for(j=i;j<=m;j++)
                {
                    sum=0;
                    for(k=1;k<=n;k++)
                    {
                        if(sum<0)
                        {
                            sum=0;
                        }
                        sum+=map[k][j]-map[k][i-1];//每一行再进行线性就可以实现二维数组的动态规划！
                        if(sum>maxs)
                        {
                            maxs=sum;
                        }
                    }
                }
            }
            cout<<maxs<<endl;
        }
    }

[Link 1]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%5B%E8%8B%97%E6%A0%8B%E6%A0%8B%5D%E5%8E%9F%E5%88%9B
[Link 2]: http://acm.nyist.net/JudgeOnline/profile.php?userid=%E8%8B%97%E6%A0%8B%E6%A0%8B