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

题目描述

给出一个N [2<=N<=100]，并给出一个N*N的矩阵，矩阵中的数为[-127,127]之间。求出矩阵中一块子矩阵的最大和。

比如：

思路

DP，枚举开始结尾两列+前缀和+最大子序列问题。

a[k][j]-a[k][i-1]==第k行第i-j的数的和

代码

#include
   
    int n,i,j,k,s,ans,a[101][101]={0};int main(){	scanf("%d",&n);	for(i=1;i<=n;i++)	  for(j=1;j<=n;j++){	  	scanf("%d",&a[i][j]);	  	a[i][j]=a[i][j]+a[i][j-1]; //求前缀和	  }	ans=-1000000;    //emmmmmm，不解释	for(i=1;i<=n;i++)	  for(j=i;j<=n;j++){   //枚举开始和结尾两列	  	s=0;     	  	for(k=1;k<=n;k++){       //以第k行开始到n求最大子序列	  		if(s+(a[k][j]-a[k][i-1])>0) //加上是否大于0（如果小于的话那不是不如不加？			s=s+a[k][j]-a[k][i-1]; //加上这一行i-j之间的数的和			else s=0; //不加，清零			if(s>ans) ans=s;	  	}  	  }	printf("%d",ans);}