关于题目：
题目地址：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函数，原来文件打开失败就会返回空指针，打开成功就返回文件指针，貌似有点儿头绪了……
if(argc==)
{
if((in = fopen(argv[],"r+"))==NULL)
{
printf("Open file error, please make sure you have inputed right file name and location!");
return ;
}
}
else
{
printf("Only one parameter of input file name is needed!");
return ;
}
2、输入的行列数与矩阵的大小不等：
我假设input.txt文件的内容来自其他程序的输出，并且那个程序可能出现运行错误，那么我们就“顺理成章”地遇到了这种错误，遇到这种错误 怎么办？行列数小一点还好办，大不了读入的矩阵不完全，至少程序能顺利跑完，行列数都大一点儿也好办，至少我能亲眼看见程序死掉了。万一一个 大一点，一个小一点！？那就坑死人的节奏了！！！！这时候突然想到样例那个诡异的输入，“5,6，-3,8,-9，2”，原来少个“，”也会有好处！？ 那么，我就以矩阵为标准进行读入了，行列号只是用来作为一个判断，本人比较懒，并且严重不喜欢动态分配空间，铁了心搞一个固定大小的数组，输 入的数组大了的话就对不起了，爷不给你算了！这用户两头要讲究一点儿嘛，说多大就多大，买张饼你想换个大的还得另加钱呢！
fscanf(in,"%d,%d,",&row,&column);
if(row>Max_R||column>Max_C)
{
printf("Come on! Don't break rules of our deal!");
return ;
}
3、输入的数字并非合法数字：
我笃定”Everything is possible”，那么，我们需要判断每个输入的数字是否是个合法的数字，再次翻出手册，然后又尝试了几下，scanf同志还 是很地道的，输入的是数字他就吃进来，输入的不是数字就放到后面等着，还很人性的返回个“0”
if(fscanf(in,"%d,%d",&row,&column)!=)
{
printf("%d %d",row,column);
printf("Row Column number illegal!");
system("pause");
return ;
}
fgetc(in);
if(row>Max_R||column>Max_C)
{
printf("Come on! Don't break rules of our deal!");
system("pause");
return ;
}
printf("%d %d",row,column);
for(i=,endflag=;i<row;i++)
{
for(j=;j<column;j++)
{ endflag=fscanf(in,"%d",&matrix[i][j]);
if(endflag==)
{
printf("Matrix number illegal!");
system("pause");
return ;
}
if(endflag==EOF)
break;
c=fgetc(in);
if(c!=',')
if(j!=column-)
{
printf("Shit problem!");
system("pause");
return ;
}
else
break;
//printf("%d%c",matrix[i][j],c);
}
if(endflag==EOF)
if(i!=row-)
{
printf("Shit problem!");
system("pause");
return ;
}
else
break;
}
不得不吐槽一把，容错处理好是一个“D”疼，中间测试了各种问题和不出问题的结果，各种截图会撑爆这篇博客的！！！，在此上一张图请注意问题的名称，感受一下我 当时的心情！！！
4、输入数字、运行结果溢出：
在第一天看这个题的时候，我和一个搞竞赛的“大牛”讨论过这个问题，他竟然说出了用“高精度”，我勒个擦的，当年写C语言作业就对这个玩 意儿有了阴影，就不手写了，重申一下，我是个比较懒的人，搞那么大的矩阵还要搞那么大的数！我真心不想给你算出结果来，于是，我这样处理，得 知long long int类型的数是有范围的（-9223372036854775808~9223372036854775807），那么，我搞一个字符串存这两个值的一半，如果你的输入中 的数有超过我的半值范围的，不好意思，我就不给你算了。至于结果嘛，我要弄一个乘数一个模最值的余数，用两个部分表示。
我的方法实在是又有点投机取巧了，于是好好学习了一把高精度整数加法，附上链接一枚：
http://blog.csdn.net/tukangzheng/article/details/6918922
#include<stdio.h>
#include<stdlib.h>
#define Max_R 10000
#define Max_C 10000
long long matrix[Max_R][Max_C];
long long Min=-;
long long Max=;
int main(int argc, char *argv[])
{
int i,j,row,column,endflag,multtem=,mult=;
long long tempsub,minsub,maxsub;
char c;
FILE *in;
if(argc>=)
{
if((in = fopen(argv[argc-],"r+"))==NULL)
{
printf("%s %s Open file error, please make sure you have inputed right file name and location!",argv[],argv[]);
system("pause");
return ;
}
}
else
{
printf("%d,Only one parameter of input file name is needed!",argc);
system("pause");
return ;
}
//printf("%d",fscanf(in,"%d,%d,",&row,&column));
if(fscanf(in,"%d,%d",&row,&column)!=)
{
printf("%d %d",row,column);
printf("Row Column number illegal!");
system("pause");
return ;
}
fgetc(in);
if(row>Max_R||column>Max_C)
{
printf("Come on! Don't break rules of our deal!");
system("pause");
return ;
}
printf("%d %d",row,column);
for(i=,endflag=;i<row;i++)
{
for(j=;j<column;j++)
{ endflag=fscanf(in,"%lld",&matrix[i][j]);
if(matrix[i][j]>Max||matrix[i][j]<Min)
{
printf("Please! I can't handle that");
system("pause");
return ;
}
if(endflag==)
{
printf("Matrix number illegal!");
system("pause");
return ;
}
if(endflag==EOF)
break;
c=fgetc(in);
if(c!=',')
if(j!=column-)
{
printf("Shit problem!");
system("pause");
return ;
}
else
break;
//printf("%d%c",matrix[i][j],c);
}
if(endflag==EOF)
if(i!=row-)
{
printf("Shit problem!");
system("pause");
return ;
}
else
break;
}
if(row==)
{
tempsub=;
//to get the minimum maxsub, find the minimum subarray;
for(i=;i<column;i++)
{
if(i==)
minsub=matrix[][];
if(minsub>matrix[][i])
minsub=matrix[][i];
}
maxsub=minsub;
for(i=;i<column;i++)
{
if(multtem>||tempsub+matrix[][i]>matrix[][i])
tempsub=tempsub+matrix[][i];
else
tempsub=matrix[][i];
if(tempsub>Max)
{
tempsub-=Max;
multtem++;
}
if(tempsub<Min)
{
tempsub+=Max;
multtem--;
}
if(tempsub>maxsub)
{
maxsub=tempsub;
mult=multtem;
}
}
printf("Multiplier:%d Remainder:%lld\n",mult,maxsub);
system("pause");
return ;
}
}
这是处理完第四个问题的代码，下面是运行的结果们：
输入文件：
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函数中：
if(getsmatrix(in,row,column)==)
{
system("pause");
return ;
}
printf("MaxSubmatrix:%d",MaxStep2(row,column));
system("pause");
return ;
getsmatric函数：
int getsmatrix(FILE *in,int row, int column)
{
int i,j,endflag;
char c;
for(i=,endflag=;i<row;i++)
{
for(j=;j<column;j++)
{ endflag=fscanf(in,"%d",&smatrix[i][j]);
if(smatrix[i][j]>Max||smatrix[i][j]<Min)
{
printf("Please! I can't handle that");
//system("pause");
return ;
}
if(endflag==)
{
printf("Matrix number illegal!");
//system("pause");
return ;
}
if(endflag==EOF)
break;
c=fgetc(in);
if(c!=',')
if(j!=column-)
{
printf("Shit problem!");
//system("pause");
return ;
}
else
break;
//printf("%d%c",matrix[i][j],c);
}
if(endflag==EOF)
if(i!=row-)
{
printf("Shit problem!");
//system("pause");
return ;
}
else
break;
}
return ;
}
（PS：这个函数是专门为非特别大的数准备的，我一直很怀疑long long型的变量计算起来会多消耗不止一两倍的时间，于是搞了一份int型的，毕竟超时死得更惨烈一些）
MaxStep2函数：
int MaxStep2(int row, int column)
{
int i,j,k,tempsub,maxsub,temparray[];
//calculate sub;
//memset(smatrix,0,sizeof(smatrix));
for(i=;i<row;i++)
{
for(j=;j<column;j++)
if(i==)
record[i][j]=smatrix[i][j];
else
record[i][j]=record[i-][j]+smatrix[i][j];
}
for(i=,maxsub=smatrix[][];i<row;i++)
{
for(j=;j<=i;j++)
{
if(j==)
tempsub=MaxSubarr(record[i],column);
else
{
for(k=;k<column;k++)
temparray[k]=record[i][k]-record[j-][k];
tempsub=MaxSubarr(temparray,column);
}
maxsub=MyMax(tempsub,maxsub);
}
}
return maxsub;
}
测试数据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次方优解”还是可以接受的。我的贪心策略：利用规则子矩阵得到一个解——>对子矩阵轮廓进行扩展，加入邻接正值，删除边上负值……
void MaxStep3(FILE *in,int row, int column)
{
int i,j,k,tempsub,maxsub,temparray[Max_C],cstart,cend,rstart,rend;
struct SubarrayInfo sub;
if(getsmatrix(in,row,column)==)
return ;
//calculate sub;
for(i=;i<row;i++)
{
for(j=;j<column;j++)
if(i==)
record[i][j]=smatrix[i][j];
else
record[i][j]=record[i-][j]+smatrix[i][j];
}
for(i=,maxsub=smatrix[][];i<row;i++)
{
for(j=;j<=i;j++)
{
if(j==)
{
sub=IMaxSub(record[i],column);
tempsub=sub.max;
}
else
{
for(k=;k<column;k++)
temparray[k]=record[i][k]-record[j-][k];
sub=IMaxSub(temparray,column);
tempsub=sub.max;
}
if(tempsub>maxsub)
{
maxsub=tempsub;
cstart=sub.start;
cend=sub.end;
rstart=j;
rend=i;
}
}
}
maxsub=AMaxSub(rstart,rend,cstart,cend,row,column,maxsub);
printf("Step3---MaxSubmatrix:%d",maxsub);
}
struct SubarrayInfo IMaxSub(int *a,int n)
{
int tempsub,maxsub,start,tempstart=,end;
int i;
struct SubarrayInfo sub;
tempsub=;
maxsub=a[n-];
for(i=;i<n;i++)
{
if(tempsub+a[i]<a[i])
{
tempstart=i;
tempsub=a[i];
}
else
tempsub+=a[i];
if(tempsub>maxsub)
{
maxsub=tempsub;
start=tempstart;
end=i;
}
}
sub.max=maxsub;
sub.start=start;
sub.end=end;
return sub;
}
int AMaxSub(int rstart,int rend,int cstart,int cend,int row,int column,int maxsub)
{
int flag[Max_R][Max_C],i,j;
memset(flag,,sizeof(flag));
for(i=rstart;i<=rend;i++)
for(j=cstart;j<=cend;j++)
flag[i][j]=;
while(rstart>||rend<row-||cstart>||cend<column-)
{
if(rstart>)
for(rstart--,i=cstart;i<column&&i<=cend&&i<column;i++)
if(flag[rstart+][i]==&&smatrix[rstart][i]>=)
{
flag[rstart][i]=;
maxsub+=smatrix[rstart][i];
}
if(rend<row-)
for(rend++,i=cstart;i<=cend&&i<column;i++)
if(flag[rend-][i]==&&smatrix[rend][i]>+)
{
flag[rend][i]=;
maxsub+=smatrix[rend][i];
}
if(cstart>)
for(cstart--,j=rstart;j<=rend&&j<row;j++)
if(flag[cstart-][j]==&&smatrix[cstart][j]>=)
{
flag[cstart][j]=;
maxsub+=smatrix[cstart][j];
}
if(cend<column-)
for(cend++,j=rstart;j<=rend&&j<row;j++)
if(flag[cend+][j]==&&smatrix[cend][j]>=)
{
flag[cend][j]=;
maxsub+=smatrix[cend][j];
}
}
return maxsub;
}
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“
照例，贴上源代码+部分测试
void MaxStep4H(FILE *in,int row, int column)
{
int i,j,k,tempsub,maxsub,temparray[];
if(getsmatrix(in,row,column)==)
return ;
//calculate sub;
//memset(smatrix,0,sizeof(smatrix));
for(i=;i<row;i++)
{
for(j=;j<column;j++)
if(i==)
record[i][j]=smatrix[i][j];
else
record[i][j]=record[i-][j]+smatrix[i][j];
}
for(i=,maxsub=smatrix[][];i<row;i++)
{
for(j=;j<=i;j++)
{
if(j==)
tempsub=LMaxSubarr(record[i],column);
else
{
for(k=;k<column;k++)
temparray[k]=record[i][k]-record[j-][k];
tempsub=LMaxSubarr(temparray,column);
}
maxsub=MyMax(tempsub,maxsub);
}
}
printf("Step4H---MaxSubmatrix:%d",maxsub);
}
int LMaxSubarr(int *a, int n)
{
int tempsub,maxsub,doua[];
int i,j;
for(i=;i<n;i++)
doua[i]=a[i];
for(j=;i<*n;j++,i++)
doua[i]=a[j];
maxsub=a[n-];
for(i=;i<n;i++)
for(j=i,tempsub=;j<i+n;j++)
{
tempsub=MyMax(tempsub+doua[j],doua[j]);
if(tempsub>maxsub)
maxsub=tempsub;
}
return maxsub;
}
测试样例：
1,
6,
5,6,-3,8,-9,2
测试结果：
第三步：
02:32:49
实在是有点儿早了，再熬我就实在饿得受不了了，贴上垂直的代码和测试，明天继续！
void MaxStep4V(FILE *in,int row, int column)
{
int i,j,l,temp[*Max_R][Max_C],maxsub,tempsub;
if(getsmatrix(in,row,column)==)
return ;
for(i=;i<row;i++)
for(j=;j<column;j++)
temp[i][j]=smatrix[i][j];
for(l=;i<*row;i++,l++)
for(j=;j<column;j++)
temp[i][j]=smatrix[l][j];
//calculate sub;
//memset(smatrix,0,sizeof(smatrix));
for(i=,maxsub=smatrix[][];i<row;i++)
{
tempsub=NMaxStep2(temp,row,column,i);
maxsub=MyMax(tempsub,maxsub);
}
printf("Step4V---MaxSubmatrix:%d",maxsub);
}
int NMaxStep2(int a[][Max_C],int row,int column,int start)
{
int i,j,k,tempsub,maxsub,temparray[Max_C];
//calculate sub;
for(i=start,k=;i<start+row;i++,k++)
{
for(j=;j<column;j++)
if(i==start)
record[k][j]=a[i][j];
else
record[k][j]=record[k-][j]+a[i][j];
}
//printf("%d",record[start][0]);
for(i=,maxsub=smatrix[][];i<row;i++)
{
for(j=;j<=i;j++)
{
if(j==)
tempsub=MaxSubarr(record[i],column);
else
{
for(k=;k<column;k++)
temparray[k]=record[i][k]-record[j-][k];
tempsub=MaxSubarr(temparray,column);
}
maxsub=MyMax(tempsub,maxsub);
}
}
return maxsub;
}
测试数据：
3,
6,
5,6,-3,8,-9,2
-10,-10,-10,-10,-9,-9
-7,8,4,7,-9,3
输出结果：
阶段五：
这步如果只是一个规则的轮胎，那么好吧，把上一步的成果用一下的OK了，
就改了几个字母，太饿了，不测试了！！！明天还要搞状压DP呢！！！还要弄单元测试！！！啊啊啊！！！！
void MaxStep5(FILE *in,int row, int column)
{
int i,j,l,temp[*Max_R][Max_C],maxsub,tempsub;
if(getsmatrix(in,row,column)==)
return ;
for(i=;i<row;i++)
for(j=;j<column;j++)
temp[i][j]=smatrix[i][j];
for(l=;i<*row;i++,l++)
for(j=;j<column;j++)
temp[i][j]=smatrix[l][j];
//calculate sub;
//memset(smatrix,0,sizeof(smatrix));
for(i=,maxsub=smatrix[][];i<row;i++)
{
tempsub=NMaxStep2(temp,row,column,i);
maxsub=MyMax(tempsub,maxsub);
}
printf("Step4V---MaxSubmatrix:%d",maxsub);
}
int NMaxStep3(int a[][Max_C],int row,int column,int start)
{
int i,j,k,tempsub,maxsub,temparray[Max_C];
//calculate sub;
for(i=start,k=;i<start+row;i++,k++)
{
for(j=;j<column;j++)
if(i==start)
record[k][j]=a[i][j];
else
record[k][j]=record[k-][j]+a[i][j];
}
//printf("%d",record[start][0]);
for(i=,maxsub=smatrix[][];i<row;i++)
{
for(j=;j<=i;j++)
{
if(j==)
tempsub=LMaxSubarr(record[i],column);
else
{
for(k=;k<column;k++)
temparray[k]=record[i][k]-record[j-][k];
tempsub=LMaxSubarr(temparray,column);
}
maxsub=MyMax(tempsub,maxsub);
}
}
return maxsub;
}
感想收获：
不得不说，这就一门C语言用得还凑合实在是受不了（le），我要尝试一下C++甚至C#，以前都接触过一点点，不用就扔了；这C语言学得也是很渣，要是有函数指针什么的，代码不会搞得这么多；学一学算法吧，看着大神们张嘴就各种DP各种复杂度，感觉自己太次了。
还差一个单元测试！！！！
