结组成员：信1201-1柴珏辉 信1201-2邓锐
一、要求
1、题目:
返回一个二维数组中最大子数组的和。
2、要求：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
程序要使用的数组放在一个叫 input.txt 的文件中, 文件格式是:
数组的行数,
数组的列数,
每一行的元素, (用逗号分开)
每一个数字都是有符号32位整数, 当然, 行数和列数都是正整数
将上述题目的各个结果转换成图形界面显示。
3、结对开发要求:
两人结对完成编程任务。
一人主要负责程序分析，代码编程。
一人负责代码复审和代码测试计划。
发表一篇博客文章讲述两人合作中的过程、体会以及如何解决冲突(附结对开发的工作照)。
二、设计思路
使用枚举法，遍历所有数据（（x，y）代表第x行第y列的数），从（1，1）列开始，到（1,2）时（1,1）+（1,2）；到（2,1）时（1,1）+（2,1）；到（2,2）时（1,1）+（1,2）+（2,1）+（2,2）……以此类推，计算出这样组成的所有子数组的和，求出其中的最大值及其对应的子数组。数组随机产生，一定范围内可改变行列数。不过写入文件并读取未实现。
三、程序代码
1 #include<iostream.h> 2 #include<stdio.h> 3 #include<stdlib.h> 4 #include<time.h> 5 #define N 3 //行数 6 #define M 5 //列数 7 void qiuhe(int a[N][M],int &he,int i,int j,int k,int l) //求两个顶点数所确定的矩阵之和，[i,j]为第一个数的下标，[k,l]为第二个数的下标 8 { 9 int c,b; 10 he=0; 11 for(c=i;c<=k;c++) 12 { 13 for(b=j;b<=l;b++) 14 { 15 he=he+a[c][b]; 16 } 17 } 18 } 19 void display(int a[N][M],int i,int j,int k,int l) //输出两个顶点数所确定的矩阵，[i,j]为第一个数的下标，[k,l]为第二个数的下标 20 { 21 int b,c; 22 for(c=i;c<=k;c++) 23 { 24 for(b=j;b<=l;b++) 25 { 26 cout<<a[c][b]<<" "; 27 } 28 cout<<endl; 29 } 30 } 31 void main() 32 { 33 int a[N][M]; 34 srand((unsigned)time(NULL)); 35 int i,j,k,l,hang1=0,hang2=0,lie1=0,lie2=0,max=a[0][0],he=0; 36 for(i=0;i<N;i++) //对二维数组中的数随机生成 37 { 38 for(j=0;j<M;j++) 39 { 40 a[i][j]=rand()%20-10; 41 } 42 } 43 for(i=0;i<N;i++) 44 { 45 for(j=0;j<M;j++) //前两个循环遍历第一个顶点数 46 { 47 for(k=i;k<N;k++) 48 { 49 for(l=j;l<M;l++) //后两个循环遍历第二个顶点数 50 { 51 qiuhe(a,he,i,j,k,l); 52 if(he>max) 53 { 54 max=he; 55 hang1=i; 56 hang2=k; 57 lie1=j; 58 lie2=l; 59 } 60 } 61 } 62 } 63 } 64 cout<<"原数组："<<endl; 65 display(a,0,0,N-1,M-1); 66 cout<<"最大子数组(两个顶点坐标（"<<hang1<<","<<lie1<<"）"<<"（"<<hang2<<","<<lie2<<"）)"<<endl; 67 display(a,hang1,lie1,hang2,lie2); 68 cout<<"和为："<<max<<endl; 69 }
截图：
四、测试
将代码随机产生数组内容部分去掉，改为固定数组，通过修改其中数据进行测试。
1.测试数据
0,0,0,0,0
0,0,0,0,0
0,0,0,0,0
2. 测试数据
1,2,3,4,5
6,7,8,9,10
11,12,13,14,15
3.测试数据
-1,-2,-3,-4,-5
-6,-7,-8,-9,-10
-11,-12,-13,-14,-15
五、心得体会
这次关键问题在于对简单算法的思考。我们开始想到了遍历的方法，即把每种可能性都计算出来再找最大，但是这种方法实现起来势必耗费时间，尤其在数据量加大的时候。我们一时间陷入僵局，暂停了一两天。随后我们从网上搜索了一些方法，又交流了看法，觉得所能想到的简便的算法都有不足之处，最终还是采用遍历的方法,但数组存在txt文件中未实现。他负责编写完程序，然后我复审，最后又一起讨论修改。我改变数据进行了测试。
这次难度提升，对合作也有了进一步的考验。过程中出现过几次分歧，比第一次合作要大些，不过也是互相阐述清楚后综合，小组正在逐步默契。
结组成员照片：
