POJ 1050 二维最大子矩阵

 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 

posted on 2011-11-29 20:42 四也 阅读(445) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年11月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜