这题是最大子序列和(hdu1003)的拓展。
先复习一下最大子序列和(DP,hdu1003)吧:
思路:用dp[i]表示以第i个数为结尾的子序列和最大值;
状态转移方程:
dp[i]= a[i] (dp[i-1]<0)
dp[i]= dp[i-1]+a[i] (dp[i-1]>=0)
这是有数组的做法。程序本人不提供
下面提供一个无数组的代码,其实思想还是一样的
hdu1003
hdu1003 #include<stdio.h> int main() { int n,s,e,max,maxs,maxe,i,num,T,sum,u=0; scanf("%d",&T); while(u++<T) { scanf("%d",&n); sum=0;max=-20000000; for(s=e=i=1;i<=n;i++) { scanf("%d",&num); sum+=num; e=i; if(max<sum){maxs=s;maxe=e;max=sum;} if(sum<0){s=i+1;sum=0;} } printf("Case %d:\n%d %d %d\n",u,max,maxs,maxe); if(u!=T)printf("\n"); } return 0; }
复习一完了最大子序列和(DP,hdu1003),好好想一想解题思路(zoj1074)。
思路:求最大子矩阵和的时候,思路是取出两行i,j,把这两行之间同一列的都加起来形成另外一个数组,求这个数组的最大子段和,求出来的这个和,就是这两行之间高度为i-j的子矩阵中最大的和。
POJ1050
#include<stdio.h> #include<string.h> int a[101][101],n,temp[101]; int solve()//最大子序列和函数 { int i,sum=0,max=0; for(i=0;i<n;i++) { sum+=temp[i]; if(sum<0)sum=0; if(sum>max)max=sum; } return max; } int main() { int i,j,k,max; while(scanf("%d",&n)!=EOF) { for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&a[i][j]); max=0; for(i=0;i<n;i++) { memset(temp,0,sizeof(temp)); for(j=i;j<n;j++) //j表示行 { for(k=0;k<n;k++) //k表示列 { temp[k]+=a[j][k]; } if(max<solve())max=solve(); } } printf("%d\n",max); } return 0; }