nyoj 104-最大和-白红宇

nyoj 104-最大和

阅读量：3904 次

发布时间：2019-05-23

本文共 1352 字，大约阅读时间需要 4 分钟。

题目描述:

给定一个由整数组成二维矩阵（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
   
    <=100）,表示有n组测试数据；每组测试数据：第一行有两个的整数r，c（0
    
     <=100），r、c分别代表矩阵的行和列；随后有r行，每行有c个整数；

输出描述:

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

样例输入:

复制

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

样例输出:

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=105;int n;int r,c;int Map[maxn][maxn];int ans;int Max;void init(){    ans=Max=0;    for (int i=0;i<=c;i++)        Map[0][i]=0;}int main(){    scanf("%d",&n);    while (n--)    {        scanf("%d%d",&r,&c);        init();        for (int i=1;i<=r;i++)        {            for (int j=1;j<=c;j++)            {                scanf("%d",&Map[i][j]);                Map[i][j]+=Map[i-1][j];            }        }        ans=Map[1][1];        for (int i=0;i<=r;i++)        {            for (int j=i+1;j<=r;j++)            {                Max=0;                for (int k=1;k<=c;k++)                {                    int temp=Map[j][k]-Map[i][k];                    if(Max>=0)                        Max+=temp;                    else                        Max=temp;                    ans=max(ans,Max);                }            }        }        printf("%d\n",ans);    }    return 0;}