杭电1081――to the max(动态规划和暴力法解) - c++编程基础

即是最大值）b[j]=a[j]。故b[j]的动态规划递归式为 b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n。
2、最大子矩阵和

矩阵是二维的，将其压缩成一维就可以用上面的方法求出最大子矩阵和了
即将一层层的数相加，压缩成一维的即可，我们遍历所有的压缩可能，就可以通过上面的方法，求出最大值！
*/
for(i=0;i {
memset(sum,0,sizeof(sum));
for(k=i;k {
for(j=0;j sum[j]=arr[k][j]+sum[j];
dp[0]=sum[0];
for(p=1;p {
if (dp[p-1]>0) dp[p]=dp[p-1]+sum[p];
else dp[p]=sum[p];

if (dp[p]>max) max=dp[p];
/*
if(dp[p-1]+sum[p]>sum[p])
dp[p]=dp[p-1]+sum[p];
else
dp[p]=dp[p-1];
if(dp[p]>max) max=dp[p];
*/
}

}
}
cout< //system("pause");
}
return 0;
}

杭电1081――to the max(动态规划和暴力法解)(二)