蓝桥杯---最大子阵

问题描述

　　给定一个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行的和，然后枚举的时候只需枚举一个行的开始，和行的结束，然后对这个范围的所有列（即m的值）进行最大子段和的dp就OK啦，这一过程中不断维护最大值；
其实最后还是转化为求一维数组的最大子段和的最大值

虽然这道题比较简单，但是比较典型，也算是个DP吧。。。

#include <iostream>
#include <cstring>
using namespace std;
#define inf 0x3f3f3f3f;
int n,m;
int a[505][505],b[505],dp[505];
int res=-inf;
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
	   for(int j=0;j<m;j++)
	      cin>>a[i][j];
    for(int x=0;x<n;x++){//设置起始行 
        memset(b,0,sizeof(b));//设置结束行 
        for(int y=x;y<n;y++){
            for(int j=0;j<m;j++)
			    b[j]+=a[y][j];//b存储第起始行x到y行到中每一列的值 
            dp[0]=b[0];
            
            if(dp[0]>res)//不要忘了这个 
			    res=dp[0];
			    
            for(int i=1;i<m;i++){
                if(dp[i-1]<0)
				    dp[i]=b[i];
                else 
				   dp[i]=dp[i-1]+b[i];
				  	 
                if(dp[i]>res)          //维护最后的结果 
				   res=dp[i];
            }
  
        }
    }
    cout<<res<<endl;
    return 0;
}

开始找到一种比较笨拙的类似方法，不过使用了sum这个数组的中间变量来记录前i行第j列的和，开始看到这个代码好有误解性啊。

#include <iostream>
#include <stdio.h>
#define N 510
#define INF 0x3f3f3f3f  //无穷大 
using namespace std;
int n, m,map[N][N],sum[N][N];

int mymax(int *p)//从i行到j行的临时数组temp求和（dp） 
{
    int b=0,max=-INF;
    for(int i=0;i<m;i++) {
        b+=p[i];
        if(b>max)   max=b;
        if(b<0)    b=0;
    }
    return max;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++){
            scanf("%d", &map[i][j]);
            if (i==0)
                sum[i][j]=map[0][j];
            else 
                sum[i][j]=sum[i-1][j]+map[i][j];//sum中存储前i行第j列的和 
        }
    }
    int max=-INF;   //无穷小
    for (int i=0;i<n;i++) {//设置起始行 
        for (int j=i;j<n;j++) {//设置结束行 
            int temp[N];
            for (int k=0;k<m;k++){ //b存储第起始行y行到当前行的值   
               if (i==0) 
			     temp[k]=sum[j][k];
               else
			     temp[k]=sum[j][k]-sum[i-1][k];
            }
			int xx=mymax(temp);
            if ( xx>max)
                max=xx;
		}
    }
    printf("%d
", max);
    return 0;
}