#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; }
一步一步往上爬。