现代程序设计——homework-02

关于题目：

　　题目地址：http://www.cnblogs.com/xinz/p/3318230.html

　　首先，不得不说自从写完第一次作业，我就开始“抠”这个题，第一眼看这个题就感觉好“坑”，读一遍之后什么都木有发现，满满的一头雾水。连题目的描述都木有看明白！如图：文件格式描述中的输入数据格式是“每一行的元素，”样例元素是“5,6，-3,8,-9，2”。那么，“2”这个行末元素后面要不要加个逗号呢？32位有符号整数是默认成二进制表示的？我们假设输入格式是有“，”并且老师不会搞一个32位的十进制整数搞死我们。那么，可以的开始我们的苦逼解题之路：

解题之路：

阶段一：

第一步：

　　容错问题看起来有很多的样子：

文件打开错误处理；
输入的行列数与矩阵大小不等；
输入的数字并非合法数字；
输入数字、运算结果溢出；

　　。

瞬间头大的感觉，我们还是一条一条开始慢慢解决吧！

1、文件打开错误处理：

　　写了一个暑假的Html和JavaSript，感觉命令行程序已经好久没碰过了，好陌生的感觉。翻一翻C语言的手册吧……在Stander I/O 里面找到了fopen函数，原来文件打开失败就会返回空指针，打开成功就返回文件指针，貌似有点儿头绪了……

 1 if(argc==2)
 2     {
 3         if((in = fopen(argv[1],"r+"))==NULL)
 4         {
 5             printf("Open file error, please make sure you have inputed right file name and location!");
 6             return 0;
 7         }
 8     }
 9     else
10     {
11         printf("Only one parameter of input file name is needed!");
12         return 0;
13     }

　　2、输入的行列数与矩阵的大小不等：

　　　　我假设input.txt文件的内容来自其他程序的输出，并且那个程序可能出现运行错误，那么我们就“顺理成章”地遇到了这种错误，遇到这种错误　　　怎么办？行列数小一点还好办，大不了读入的矩阵不完全，至少程序能顺利跑完，行列数都大一点儿也好办，至少我能亲眼看见程序死掉了。万一一个　　　大一点，一个小一点！？那就坑死人的节奏了！！！！这时候突然想到样例那个诡异的输入，“5,6，-3,8,-9，2”，原来少个“，”也会有好处！？　　　那么，我就以矩阵为标准进行读入了，行列号只是用来作为一个判断，本人比较懒，并且严重不喜欢动态分配空间，铁了心搞一个固定大小的数组，输　　　入的数组大了的话就对不起了，爷不给你算了！这用户两头要讲究一点儿嘛，说多大就多大，买张饼你想换个大的还得另加钱呢！　

1 fscanf(in,"%d,%d,",&row,&column);
2 if(row>Max_R||column>Max_C)
3 {
4     printf("Come on! Don't break rules of our deal!");
5     return 0;
6 }

　　3、输入的数字并非合法数字：

　　　　我笃定"Everything is possible"，那么，我们需要判断每个输入的数字是否是个合法的数字，再次翻出手册，然后又尝试了几下，scanf同志还　　　是很地道的，输入的是数字他就吃进来，输入的不是数字就放到后面等着，还很人性的返回个“0”

 1 if(fscanf(in,"%d,%d",&row,&column)!=2)
 2     {
 3         printf("%d %d",row,column);
 4         printf("Row Column number illegal!");
 5         system("pause");
 6         return 0;
 7     }
 8     fgetc(in);
 9     if(row>Max_R||column>Max_C)
10     {
11         printf("Come on! Don't break rules of our deal!");
12         system("pause");
13         return 0;
14     }
15     printf("%d %d",row,column);
16     for(i=0,endflag=0;i<row;i++)
17     {
18         for(j=0;j<column;j++)
19         {
20             
21             endflag=fscanf(in,"%d",&matrix[i][j]);
22             if(endflag==0)
23             {
24                 printf("Matrix number illegal!");
25                 system("pause");
26                 return 0;
27             }
28             if(endflag==EOF)
29                 break;
30             c=fgetc(in);
31             if(c!=',')
32                 if(j!=column-1)
33                 {
34                     printf("Shit problem!");
35                     system("pause");
36                     return 0;
37                 }
38                 else
39                     break;
40             //printf("%d%c",matrix[i][j],c);
41         }
42         if(endflag==EOF)
43             if(i!=row-1)
44             {
45                 printf("Shit problem!");
46                 system("pause");
47                 return 0;
48             }
49             else
50                 break;
51     }

　　　　不得不吐槽一把，容错处理好是一个“D”疼，中间测试了各种问题和不出问题的结果，各种截图会撑爆这篇博客的！！！，在此上一张图请注意问题的名称，感受一下我　　　当时的心情！！！

　　4、输入数字、运行结果溢出：

　　　　在第一天看这个题的时候，我和一个搞竞赛的“大牛”讨论过这个问题，他竟然说出了用“高精度”，我勒个擦的，当年写C语言作业就对这个玩　　　意儿有了阴影，就不手写了，重申一下，我是个比较懒的人，搞那么大的矩阵还要搞那么大的数！我真心不想给你算出结果来，于是，我这样处理，得　　　知long long int类型的数是有范围的（-9223372036854775808~9223372036854775807），那么，我搞一个字符串存这两个值的一半，如果你的输入中　　　的数有超过我的半值范围的，不好意思，我就不给你算了。至于结果嘛，我要弄一个乘数一个模最值的余数，用两个部分表示。

　　　　我的方法实在是又有点投机取巧了，于是好好学习了一把高精度整数加法，附上链接一枚：

　　　　　　http://blog.csdn.net/tukangzheng/article/details/6918922

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #define Max_R 10000
  4 #define Max_C 10000
  5 long long matrix[Max_R][Max_C];
  6 long long Min=-4611686018427387905;
  7 long long Max=4611686018427387904;
  8 int main(int argc, char *argv[])
  9 {
 10     int i,j,row,column,endflag,multtem=0,mult=0;
 11     long long tempsub,minsub,maxsub;
 12     char c;
 13     FILE *in;
 14     if(argc>=2)
 15     {
 16         if((in = fopen(argv[argc-1],"r+"))==NULL)
 17         {
 18             printf("%s %s Open file error, please make sure you have inputed right file name and location!",argv[0],argv[1]);
 19             system("pause");
 20             return 0;
 21         }
 22     }
 23     else
 24     {
 25         printf("%d,Only one parameter of input file name is needed!",argc);
 26         system("pause");
 27         return 0;
 28     }
 29     //printf("%d",fscanf(in,"%d,%d,",&row,&column));
 30     if(fscanf(in,"%d,%d",&row,&column)!=2)
 31     {
 32         printf("%d %d",row,column);
 33         printf("Row Column number illegal!");
 34         system("pause");
 35         return 0;
 36     }
 37     fgetc(in);
 38     if(row>Max_R||column>Max_C)
 39     {
 40         printf("Come on! Don't break rules of our deal!");
 41         system("pause");
 42         return 0;
 43     }
 44     printf("%d %d",row,column);
 45     for(i=0,endflag=0;i<row;i++)
 46     {
 47         for(j=0;j<column;j++)
 48         {
 49             
 50             endflag=fscanf(in,"%lld",&matrix[i][j]);
 51             if(matrix[i][j]>Max||matrix[i][j]<Min)
 52             {
 53                 printf("Please! I can't handle that");
 54                 system("pause");
 55                 return 0;
 56             }
 57             if(endflag==0)
 58             {
 59                 printf("Matrix number illegal!");
 60                 system("pause");
 61                 return 0;
 62             }
 63             if(endflag==EOF)
 64                 break;
 65             c=fgetc(in);
 66             if(c!=',')
 67                 if(j!=column-1)
 68                 {
 69                     printf("Shit problem!");
 70                     system("pause");
 71                     return 0;
 72                 }
 73                 else
 74                     break;
 75             //printf("%d%c",matrix[i][j],c);
 76         }
 77         if(endflag==EOF)
 78             if(i!=row-1)
 79             {
 80                 printf("Shit problem!");
 81                 system("pause");
 82                 return 0;
 83             }
 84             else
 85                 break;
 86     }
 87     if(row==1)
 88     {
 89         tempsub=0;
 90         //to get the minimum maxsub, find the minimum subarray;
 91         for(i=0;i<column;i++)
 92         {
 93             if(i==0)
 94                 minsub=matrix[0][0];
 95             if(minsub>matrix[0][i])
 96                 minsub=matrix[0][i];
 97         }
 98         maxsub=minsub;
 99         for(i=0;i<column;i++)
100         {
101             if(multtem>0||tempsub+matrix[0][i]>matrix[0][i])
102                 tempsub=tempsub+matrix[0][i];
103             else
104                 tempsub=matrix[0][i];
105             if(tempsub>Max)
106             {
107                 tempsub-=Max;
108                 multtem++;
109             }
110             if(tempsub<Min)
111             {
112                 tempsub+=Max;
113                 multtem--;
114             }
115             if(tempsub>maxsub)
116             {
117                 maxsub=tempsub;
118                 mult=multtem;
119             }
120         }
121         printf("Multiplier:%d Remainder:%lld
",mult,maxsub);
122         system("pause");
123         return 0;
124     }
125 }

　　　　这是处理完第四个问题的代码，下面是运行的结果们：

输入文件：

1,

6,

5,6,-3,8,-9,2

输入文件：

1,

6,

5,6,3611686018427387904,4511686018427387904,2611686018427387904,1611686018427387904

阶段二：

第一步：

　　分析一把这个题，还是可以按照老套路来的无非先枚举一下，不错，O(n^2*m^2)个子矩阵，如果每个矩阵都“善良”地一个一个求和，那么这个复杂度是O(n^4*m^4)于是，有点接受不了了，然后，无非Trade Memory一把，记录一下以前的计算结果，恩恩，非常明显O(n^3*m^3)了……，当然，这还是不能接受的，我们还是坐下来谈谈动态规划吧，说实话，我没有想出来什么好的动态规划的方法，我能想到的方法最坏情况下还是能到O(n^3*m^3)的，当然，我也就没闲心去计算它的平均复杂度了，于是找“度娘”请教了一把动态规划的方法，好像看明白了。于是玩命儿码代码，然后就是“第二天”了……

　　代码加在一起实在是有点儿略长了，又是在第一个的基础上面改的，代码活生生就是一坨翔的感觉了，而且下面还有好长的路要走的！，不管怎么样，还是贴出来看一看，可能有些变量是全局变量，有些变量是在main函数里面，找起来好费劲的

　　在main函数中：

1 　　　　if(getsmatrix(in,row,column)==0)
2         {
3             system("pause");
4             return 0;
5         }
6         printf("MaxSubmatrix:%d",MaxStep2(row,column));
7         system("pause");
8         return 0;

　　getsmatric函数：

 1 int getsmatrix(FILE *in,int row, int column)
 2 {
 3     int i,j,endflag;
 4     char c;
 5     for(i=0,endflag=0;i<row;i++)
 6     {
 7         for(j=0;j<column;j++)
 8         {
 9             
10             endflag=fscanf(in,"%d",&smatrix[i][j]);
11             if(smatrix[i][j]>Max||smatrix[i][j]<Min)
12             {
13                 printf("Please! I can't handle that");
14                 //system("pause");
15                 return 0;
16             }
17             if(endflag==0)
18             {
19                 printf("Matrix number illegal!");
20                 //system("pause");
21                 return 0;
22             }
23             if(endflag==EOF)
24                 break;
25             c=fgetc(in);
26             if(c!=',')
27                 if(j!=column-1)
28                 {
29                     printf("Shit problem!");
30                     //system("pause");
31                     return 0;
32                 }
33                 else
34                     break;
35             //printf("%d%c",matrix[i][j],c);
36         }
37         if(endflag==EOF)
38             if(i!=row-1)
39             {
40                 printf("Shit problem!");
41                 //system("pause");
42                 return 0;
43             }
44             else
45                 break;
46     }
47     return 1;
48 }

　　（PS：这个函数是专门为非特别大的数准备的，我一直很怀疑long long型的变量计算起来会多消耗不止一两倍的时间，于是搞了一份int型的，毕竟超时死得更惨烈一些）

　　MaxStep2函数：

 1 int MaxStep2(int row, int column)
 2 {
 3     int i,j,k,tempsub,maxsub,temparray[1000];
 4     //calculate sub;
 5     //memset(smatrix,0,sizeof(smatrix));
 6     for(i=0;i<row;i++)
 7     {
 8         for(j=0;j<column;j++)
 9             if(i==0)
10                 record[i][j]=smatrix[i][j];
11             else
12                 record[i][j]=record[i-1][j]+smatrix[i][j];
13     }
14     for(i=0,maxsub=smatrix[0][0];i<row;i++)
15     {
16         for(j=0;j<=i;j++)
17         {
18             if(j==0)
19                 tempsub=MaxSubarr(record[i],column);
20             else
21             {
22                 for(k=0;k<column;k++)
23                     temparray[k]=record[i][k]-record[j-1][k];
24                 tempsub=MaxSubarr(temparray,column);
25             }
26             maxsub=MyMax(tempsub,maxsub);
27         }
28     }
29     return maxsub;
30 }

测试数据1：

3,
6,
5,6,-3,8,-9,2
1,-12,20,0,-3,-5
-9,-7,-3,6,7,-1

测试结果：　

测试数据2：

8,
12,
8,-10,-3,26,-11,-1,-6,12,17,6,28,4
20,-13,-20,-13,-15,-254,5,8,9,-4,-9,29
-11,18,-25,9,12,-9,-2,23,8,-1,3,-14
-16,-7,0,201,-1,309,3,6,-18,11,24,-8
-1,-7,11,100,21,292,-2,2,-18,-8,-10,9
26,-11,-19,-18,20,-981,2,-14,12,-14,1,27
9,-20,5,28,-15,26,-20,-8,-16,30,3,20
-6,-7,-5,-9,-16,-15,5,-16,22,-17,11,-18

　　测试结果2:

阶段三：

第一步：

　　在我还在做第一次作业的时候，肖神就已经在群里吵吵这个阶段不好做了，我记得当时大家在群里嚷嚷着要用状压DP、插头DP什么的，更有好事儿的还证明了一下这个问题是个NP，至少是个NPC问题，我勒个去的，他们好歹也都是搞ACM的，我等弱还是先绕路而行吧！

　　我对这个题的一系列YY，因为大神们都说了要连通性状压DP了，而且都指数级复杂度了，我就不花时间琢磨精确解的事儿了，让我得出精确解，无非直接枚举——>判断连通性——>……然后复杂度很现实O(2^(m*n)*m*n)；然后，剩下就是回溯搜索+剪枝了，因为利用连通性进行剪枝，相比于第一种做法优化效果还是很明显的，而且效果会随着矩阵的增大而更加明显。于是我就黔驴技穷了……

　　当然，我就考虑“牺牲精度”了，当时跟鲁大师讨论这个问题，我说：“直接贪心一个次优解吧”，大师说：“那就是n优解了”……于是，我就考虑用贪心做了，贪心出来一个“次的n次方优解”还是可以接受的。我的贪心策略：利用规则子矩阵得到一个解——>对子矩阵轮廓进行扩展，加入邻接正值，删除边上负值……

  1 void MaxStep3(FILE *in,int row, int column)
  2 {
  3     int i,j,k,tempsub,maxsub,temparray[Max_C],cstart,cend,rstart,rend;
  4     struct SubarrayInfo sub;
  5     if(getsmatrix(in,row,column)==0)
  6         return ;
  7     //calculate sub;
  8     for(i=0;i<row;i++)
  9     {
 10         for(j=0;j<column;j++)
 11             if(i==0)
 12                 record[i][j]=smatrix[i][j];
 13             else
 14                 record[i][j]=record[i-1][j]+smatrix[i][j];
 15     }
 16     for(i=0,maxsub=smatrix[0][0];i<row;i++)
 17     {
 18         for(j=0;j<=i;j++)
 19         {
 20             if(j==0)
 21             {
 22                 sub=IMaxSub(record[i],column);
 23                 tempsub=sub.max;
 24             }
 25             else
 26             {
 27                 for(k=0;k<column;k++)
 28                     temparray[k]=record[i][k]-record[j-1][k];
 29                 sub=IMaxSub(temparray,column);
 30                 tempsub=sub.max;
 31             }
 32             if(tempsub>maxsub)
 33             {
 34                 maxsub=tempsub;
 35                 cstart=sub.start;
 36                 cend=sub.end;
 37                 rstart=j;
 38                 rend=i;
 39             }
 40         }
 41     }
 42     maxsub=AMaxSub(rstart,rend,cstart,cend,row,column,maxsub);
 43     printf("Step3---MaxSubmatrix:%d",maxsub);
 44 }
 45 struct SubarrayInfo IMaxSub(int *a,int n)
 46 {
 47     int tempsub,maxsub,start,tempstart=0,end;
 48     int i;
 49     struct SubarrayInfo sub;
 50     tempsub=0;
 51     maxsub=a[n-1];
 52     for(i=0;i<n;i++)
 53     {
 54         if(tempsub+a[i]<a[i])
 55         {
 56             tempstart=i;
 57             tempsub=a[i];
 58         }
 59         else
 60             tempsub+=a[i];
 61         if(tempsub>maxsub)
 62         {
 63             maxsub=tempsub;
 64             start=tempstart;
 65             end=i;
 66         }
 67     }
 68     sub.max=maxsub;
 69     sub.start=start;
 70     sub.end=end;
 71     return sub;
 72 }
 73 int AMaxSub(int rstart,int rend,int cstart,int cend,int row,int column,int maxsub)
 74 {
 75     int flag[Max_R][Max_C],i,j;
 76     memset(flag,0,sizeof(flag));
 77     for(i=rstart;i<=rend;i++)
 78         for(j=cstart;j<=cend;j++)
 79             flag[i][j]=1;
 80     while(rstart>0||rend<row-1||cstart>0||cend<column-1)
 81     {
 82         if(rstart>0)
 83             for(rstart--,i=cstart;i<column&&i<=cend&&i<column;i++)
 84                 if(flag[rstart+1][i]==1&&smatrix[rstart][i]>=0)
 85                 {
 86                     flag[rstart][i]=1;
 87                     maxsub+=smatrix[rstart][i];
 88                 }
 89         if(rend<row-1)
 90             for(rend++,i=cstart;i<=cend&&i<column;i++)
 91                 if(flag[rend-1][i]==1&&smatrix[rend][i]>+0)
 92                 {
 93                     flag[rend][i]=1;
 94                     maxsub+=smatrix[rend][i];
 95                 }
 96         if(cstart>0)
 97             for(cstart--,j=rstart;j<=rend&&j<row;j++)
 98                 if(flag[cstart-1][j]==1&&smatrix[cstart][j]>=0)
 99                 {
100                     flag[cstart][j]=1;
101                     maxsub+=smatrix[cstart][j];
102                 }
103         if(cend<column-1)
104             for(cend++,j=rstart;j<=rend&&j<row;j++)
105                 if(flag[cend+1][j]==1&&smatrix[cend][j]>=0)
106                 {
107                     flag[cend][j]=1;
108                     maxsub+=smatrix[cend][j];
109                 }
110     }
111     return maxsub;
112 }

3,
6,
5,6,-3,8,-9,2
-1,-12,20,0,-3,-5
-9,-7,-3,6,7,-1,

　　（PS：陈丹琦老师的论文和ppt一时半会儿是看不懂了，等我从状压DP到连通性状压DP啃一遍再来补大神们的实现方案）

阶段四：

第一步：

　　分析一下这个问题，看着好像挺玄乎的，好好的一个矩阵还要给人连起来，弄得没法下嘴开个口来做这个题，同时当时纠结在这个“在3的基础上”会不会也要求要不规则额？？？那岂不是死翘翘的节奏了。当然，后来鲁大师说这疑问还是挺水的，于是就默认矩阵是规则的了。突破口还是在一维上，只不过先把圆圈剪开，然后扫就好了，至于怎么剪，我打算把数组按照正负相间的子段进行合并，当然，把首位两部分同号的合并，于是：

　　输入：5,6，-3,8，-9,2

　　处理：13，-3,8-9

　　对了？

　　高兴太早了，这样还是没有完全剪断前后的联系的……

　　于是，继续想，只能把每个数当头分别扫面一遍了，如果时间承受不了，可以用上面的方法优化一下长度。同理可解决垂直。

第二步：

　　终于算是高出来一个"/h“

　　照例，贴上源代码+部分测试

 1 void MaxStep4H(FILE *in,int row, int column)
 2 {
 3     int i,j,k,tempsub,maxsub,temparray[1000];
 4     if(getsmatrix(in,row,column)==0)
 5         return ;
 6     //calculate sub;
 7     //memset(smatrix,0,sizeof(smatrix));
 8     for(i=0;i<row;i++)
 9     {
10         for(j=0;j<column;j++)
11             if(i==0)
12                 record[i][j]=smatrix[i][j];
13             else
14                 record[i][j]=record[i-1][j]+smatrix[i][j];
15     }
16     for(i=0,maxsub=smatrix[0][0];i<row;i++)
17     {
18         for(j=0;j<=i;j++)
19         {
20             if(j==0)
21                 tempsub=LMaxSubarr(record[i],column);
22             else
23             {
24                 for(k=0;k<column;k++)
25                     temparray[k]=record[i][k]-record[j-1][k];
26                 tempsub=LMaxSubarr(temparray,column);
27             }
28             maxsub=MyMax(tempsub,maxsub);
29         }
30     }
31     printf("Step4H---MaxSubmatrix:%d",maxsub);
32 }
33 int LMaxSubarr(int *a, int n)
34 {
35     int tempsub,maxsub,doua[2000];
36     int i,j;
37     for(i=0;i<n;i++)
38         doua[i]=a[i];
39     for(j=0;i<2*n;j++,i++)
40         doua[i]=a[j];
41     maxsub=a[n-1];
42     for(i=0;i<n;i++)
43         for(j=i,tempsub=0;j<i+n;j++)
44         {
45             tempsub=MyMax(tempsub+doua[j],doua[j]);
46             if(tempsub>maxsub)
47                 maxsub=tempsub;
48         }
49     return maxsub;
50 }

测试样例：

1,

6,

5,6,-3,8,-9,2

　　测试结果：

第三步：

　　02:32:49

　　实在是有点儿早了，再熬我就实在饿得受不了了，贴上垂直的代码和测试，明天继续！

 1 void MaxStep4V(FILE *in,int row, int column)
 2 {
 3     int i,j,l,temp[2*Max_R][Max_C],maxsub,tempsub;
 4     if(getsmatrix(in,row,column)==0)
 5         return ;
 6     for(i=0;i<row;i++)
 7         for(j=0;j<column;j++)
 8             temp[i][j]=smatrix[i][j];
 9     for(l=0;i<2*row;i++,l++)
10         for(j=0;j<column;j++)
11             temp[i][j]=smatrix[l][j];
12     //calculate sub;
13     //memset(smatrix,0,sizeof(smatrix));
14     for(i=0,maxsub=smatrix[0][0];i<row;i++)
15     {
16         tempsub=NMaxStep2(temp,row,column,i);
17         maxsub=MyMax(tempsub,maxsub);
18     }
19     printf("Step4V---MaxSubmatrix:%d",maxsub);
20 }
21 int NMaxStep2(int a[][Max_C],int row,int column,int start)
22 {
23     int i,j,k,tempsub,maxsub,temparray[Max_C];
24     //calculate sub;
25     for(i=start,k=0;i<start+row;i++,k++)
26     {
27         for(j=0;j<column;j++)
28             if(i==start)
29                 record[k][j]=a[i][j];
30             else
31                 record[k][j]=record[k-1][j]+a[i][j];
32     }
33     //printf("%d",record[start][0]);
34     for(i=0,maxsub=smatrix[0][0];i<row;i++)
35     {
36         for(j=0;j<=i;j++)
37         {
38             if(j==0)
39                 tempsub=MaxSubarr(record[i],column);
40             else
41             {
42                 for(k=0;k<column;k++)
43                     temparray[k]=record[i][k]-record[j-1][k];
44                 tempsub=MaxSubarr(temparray,column);
45             }
46             maxsub=MyMax(tempsub,maxsub);
47         }
48     }
49     return maxsub;
50 }

测试数据：

3,
6,
5,6,-3,8,-9,2
-10,-10,-10,-10,-9,-9
-7,8,4,7,-9,3

　　输出结果：

阶段五：

　　这步如果只是一个规则的轮胎，那么好吧，把上一步的成果用一下的OK了，

　　就改了几个字母，太饿了，不测试了！！！明天还要搞状压DP呢！！！还要弄单元测试！！！啊啊啊！！！！

 1 void MaxStep5(FILE *in,int row, int column)
 2 {
 3     int i,j,l,temp[2*Max_R][Max_C],maxsub,tempsub;
 4     if(getsmatrix(in,row,column)==0)
 5         return ;
 6     for(i=0;i<row;i++)
 7         for(j=0;j<column;j++)
 8             temp[i][j]=smatrix[i][j];
 9     for(l=0;i<2*row;i++,l++)
10         for(j=0;j<column;j++)
11             temp[i][j]=smatrix[l][j];
12     //calculate sub;
13     //memset(smatrix,0,sizeof(smatrix));
14     for(i=0,maxsub=smatrix[0][0];i<row;i++)
15     {
16         tempsub=NMaxStep2(temp,row,column,i);
17         maxsub=MyMax(tempsub,maxsub);
18     }
19     printf("Step4V---MaxSubmatrix:%d",maxsub);
20 }
21 int NMaxStep3(int a[][Max_C],int row,int column,int start)
22 {
23     int i,j,k,tempsub,maxsub,temparray[Max_C];
24     //calculate sub;
25     for(i=start,k=0;i<start+row;i++,k++)
26     {
27         for(j=0;j<column;j++)
28             if(i==start)
29                 record[k][j]=a[i][j];
30             else
31                 record[k][j]=record[k-1][j]+a[i][j];
32     }
33     //printf("%d",record[start][0]);
34     for(i=0,maxsub=smatrix[0][0];i<row;i++)
35     {
36         for(j=0;j<=i;j++)
37         {
38             if(j==0)
39                 tempsub=LMaxSubarr(record[i],column);
40             else
41             {
42                 for(k=0;k<column;k++)
43                     temparray[k]=record[i][k]-record[j-1][k];
44                 tempsub=LMaxSubarr(temparray,column);
45             }
46             maxsub=MyMax(tempsub,maxsub);
47         }
48     }
49     return maxsub;
50 }

感想收获：

　　不得不说，这就一门C语言用得还凑合实在是受不了（le），我要尝试一下C++甚至C#，以前都接触过一点点，不用就扔了；这C语言学得也是很渣，要是有函数指针什么的，代码不会搞得这么多；学一学算法吧，看着大神们张嘴就各种DP各种复杂度，感觉自己太次了。

　　还差一个单元测试！！！！