[蓝桥杯][历届试题]最大子阵

大子阵"/>

[蓝桥杯][历届试题]最大子阵

题目描述：

给定一个n*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。 

其中，A的子矩阵指在A中行和列均连续的一块。 

输入

输入的第一行包含两个整数n,  m，分别表示矩阵A的行数和列数。 

接下来n行，每行m个整数，表示矩阵A。 

数据规模和约定
对于100%的数据，1< =n,  m< =500，A中每个元素的绝对值不超过5000。

输出

输出一行，包含一个整数，表示A中最大的子矩阵中的元素和。 

样例输入

3 3 
-1 -4 3
3 4 -1
-5 -2 8

样例输出

10

样例说明 
取最后一列，和为10。 

本题思路

1.先按照题目所给的要求输入数据，再以列为单位，写出每列的前缀和数组，每列的前缀和数组和行数的数组构成一个二维数组，sum[i][j];其中[i]表示的是当前所在的行数，[j]表示的是第i行第j列的前缀和。

前缀和：例如取一位置为i行j列的元素，则前缀和为第j列中第一个元素到第i个元素的和。

两元素前缀和的差可以表示为子矩阵A的宽。

图例：

代码：

void qzh(int n,int m)
{int sum[501][501]={0};//前缀和数组int a[501][501];//输入m*n矩阵for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];if(i>1)//若行数不为1，则第i行j列处元素的前缀和为它本身+它上面的前缀和。{sum[i][j]=sum[i-1][j]+a[i][j];}else if(i==1)//若行数为1，则第一行j列处的元素的前缀和为它本身。{sum[i][j]=a[i][j];}}}
}

2.确定矩阵A的范围，可以从头行，尾行，右列三个边来确定范围，设一个ans来表示矩阵A的最大值，用ans与每次求出来的矩阵和temp进行比较，从而得出最大矩阵和，temp的值=矩阵A各列的值的和，具体步骤见代码：

int ans=-99999;//表示最大矩阵A值的和for(int sou=1;sou<=n;sou++)//表示首行{for(int wei=sou;wei<=n;wei++)//表示尾行{int temp=0;//temp表示当前所求矩阵的值for(int v=1;v<=m;v++)//表示右列{int sun;sun=sum[wei][v]-sum[sou-1][v];//表示当前矩形第v列的值的和if(temp>=0)//若之前所求矩阵的值大于等于0，则加上第v列的和，并ans进行比较得出较大值{temp=temp+sun;ans=max(ans,temp);}else if(temp<0)//若之前所求矩阵的值小于0，则舍弃之前所求的值，将sun与ans进行比较得出较大值{temp=sun;ans=max(temp,ans);}}}}    cout<<ans<<endl;

完整代码如下（建议先搞懂上面两部分代码再看完整代码）：

#include<iostream>
using namespace std;
int main()
{int n,m;int sum[501][501]={0};int a[501][501];cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];if(i>1){sum[i][j]=sum[i-1][j]+a[i][j];}else if(i==1){sum[i][j]=a[i][j];}}}int ans=-99999;for(int sou=1;sou<=n;sou++){for(int wei=sou;wei<=n;wei++){int temp=0;for(int v=1;v<=m;v++){int sun;sun=sum[wei][v]-sum[sou-1][v];if(temp>=0){temp=temp+sun;ans=max(ans,temp);}else if(temp<0){temp=sun;ans=max(temp,ans);}}}}cout<<ans<<endl;return 0;
}

以上就是我对于该题的理解，如有错误请各位大佬指出。