poj1050最大子段和的二维版

#include <iostream>
#include <cstring>
#include <algorithm>
//我一定会让你们后悔的
using namespace std;
int b[105][105];
int dp[105];
int MaxSum(int n,int dp[]) //求最大子段和
{
int sum = 0,b = 0;
for(int i = 1; i<=n; ++i)
{
b = max(b+dp[i],dp[i]);
if(b>sum) sum = b;
}
return sum;
}
int main()
{
ios::sync_with_stdio(false);
int n,i,j,k,l,max=0;
memset(dp,0,sizeof(dp));
cin>>n;
for(i=1; i<=n; ++i)
{
for(j = 1; j<=n; ++j)
{
cin>>b[i][j];
b[i][j] += b[i-1][j]; //利用前缀和减少计算量
}
}
for(i=1; i<=n; ++i)
{
for(j=i; j<=n; ++j)
{
for(k=1; k<=n; ++k)
dp[k] = b[j][k]-b[i][k]; //转化为一维的最大子段和问题
l = MaxSum(n,dp);
if(l>max) max = l;
}
}
cout<<max<<endl;
return 0;
}

一步一步往上爬。