1 //解法一：自己的解法：先求每一行中从i到j的和存储在sum[r]中r从1到n,记录每一列从i到j的和。然后用
2 // 一维数组的方法求出。47MS。
3 #include<iostream>
4 using namespace std;
5 //=============================================
6 #define N 102
7 int p[N][N];
8 int b[N][N];
9 #define M 128;
10 int sum[N];
11 //==============================================
12 int Maxtri(int start,int end,int *a)//一维数组求最大子段和
13 {
14 int s=0;int max=-M;
15 for(int i=start;i<=end;++i)
16 {
17 if(s+a[i]>0)
18 {
19 s=s+a[i];
20 }
21 else
22 {
23 s=0;
24 }
25 if(s>max)max=s;
26 }
27 return max;
28 }
29
30 int main()
31 {
32 int n;
33 int m=-M;
34 cin>>n;
35 for(int i=1;i<=n;++i)
36 {
37 for(int j=1;j<=n;++j)
38 {
39 cin>>p[i][j];
40 }
41 }
42 for(int i=1;i<=n;++i)
43 {
44 for(int j=i;j<=n;++j)
45 {
46 for(int r=1;r<=n;++r)
47 {
48 sum[r]=0;//勿忘，每次都初始化。。。
49 for(int k=i;k<=j;++k)
50 {
51 sum[r]+=p[r][k];
52 }
53 }
54 if(Maxtri(1,n,sum)>m)m=Maxtri(1,n,sum);
55 }
56 }
57 cout<<m<<endl;
58 }
59