蓝桥杯训练历届试题最大子阵（只用了前缀和，没用dp写）

我就是我 2022-03-08 01:04 103阅读 0赞

**问题描述**

**　　给定一个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**

**样例说明**

**　　取最后一列，和为10。**

**数据规模和约定**

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

//可以将矩阵进行压缩，
    //用当前矩阵的第i行来表示原来矩阵的前i行，这样的话在计算的时候就可以将二维的矩阵压缩成一维来进行，
    //每次进行相应的行距的变化来变化列的数目。
    #include<iostream>
    using namespace std;
    
    int a[600][600],b[600][600];
    
    int main()
    {
    	int n,m,j,k,i,T;
    	cin>>n>>m;
    	for (i=1;i<=n;i++)
    	{
    		for (j=1;j<=m;j++)
    		{
    			cin>>a[i][j];
    		}
    	}
    	 //矩阵转换，将矩阵的第j列的值转换为前j列值的和
    	for (j=1;j<=m;j++)
    	{
    		int temp = 0;
    		for (i=1;i<=n;i++)
    		{
    			b[i][j] = b[i-1][j] + a[i][j];
    		}
    	}
    	//子矩阵相加的时候，i和j来控制行数，k来控制列数
    	int ans=-1000000000;
    	for (i=1;i<=n;i++)
    	{
    		for (j=i;j<=n;j++)
    		{
    			int temp = 0;
    			for (k=1;k<=m;k++)
    			{
    				//保证矩阵的行数是从第i行到第j行，然后列数不断变化，如果当前的子矩阵的和小于0了，那么肯定是加上了比较小的列，要重新开始计算
    				temp += b[j][k] - b[i-1][k];
    				if (temp>ans)
    				ans = temp;
    				if (temp<0)
    				temp=0;
    				
    			}
    		}
    	}
    	cout<<ans<<endl;
    	return 0;
    }