蓝桥杯历届试题最大子阵

痛定思痛。 2024-02-17 19:39 110阅读 0赞

历届试题 最大子阵

时间限制：1.0s 内存限制：256.0MB

问题描述

给定一个n\*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。  
  
　　其中，A的子矩阵指在A中行和列均连续的一块。

输入格式

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

输出格式

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

样例输入

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

样例输出

样例说明

取最后一列，和为10。

数据规模和约定

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

思路：二维转一维，那就是我们熟悉的最大字段之和了，当然这里并不是一下就直接整个二维表就转换成一维了， 如果有n行，那么就要枚举1 to n高度，对每个高度同一列之和用数组ans\[k\]储存，然后就是一维的最大字段和，具体见代码

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=500+5;
    int a[maxn][maxn];
    int ans[maxn];
    int n,m;
    
    int Max1(){
    	int tol=0;
    	int mx=ans[0];
    	for(int i=0;i<m;i++){
    		tol+=ans[i];
    		if(tol>mx)
    		  mx=tol;
    		if(tol<0){
    		  tol=0;
    		}
    	}
    	return mx;
    }
    int main(){
    	while(scanf("%d%d",&n,&m)==2){
    		for(int i=0;i<n;i++)
    		 for(int j=0;j<m;j++)
    		  scanf("%d",&a[i][j]);
    		  
    		int MaxSum=a[0][0];   //初始值不能设置为0，因为可能为负
    		for(int i=0;i<n;i++){
    			memset(ans,0,sizeof(ans));
    			for(int j=i;j<n;j++){
    				for(int k=0;k<m;k++){
    					ans[k]+=a[j][k];
    				}
    				
    				int tmp=Max1();
    				if(tmp>MaxSum)MaxSum=tmp;
    			}
    		}
    		
    		printf("%d\n",MaxSum);
    	}
    	return 0;
    }

做了这道题只想说一句：革命尚未成功，同志还需努力！！！