一、题目及要求：
1、题目：返回一个整数数组中最大子数组的和。
2、要求：
①输入一个整形数组，数组里有正数也有负数；数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和；求所有子数组的和的最大值；要求时间复杂度为O(n)。
②两人结对完成编程任务；一人主要负责程序分析，代码编程，一人负责代码复审和代码测试计划。
3、结对人员：胡亚宝 焦燕
二、设计思路：
①第一个方法，定义一个数组，将所有的子数组都列出来，再将它们的和都求出来放到该数组中，再求最大值，输出。但是在编写过程中，我们发现如果用循环方式存放，则序号不方便排，于是我们又想到边存边比，从第一个数开始，求出所有包含它的数组，依次求和，将最大值存入max。这样的确实现了要求的功能，但是时间复杂度为O（n*n）,不符合要求。
②第二个方法，我们发现，如果从第一个数开始加，加到某一值，当此时的和为负数时，无论后面是什么值，都不可能最大，则将前面的和值舍弃，直接从下一个开始加，仍旧是边加边比，直到求出最大值，此时只有一个for循环，事件复杂度为O（n）。
三、源代码：
#include "stdafx.h" 3 4 int _tmain(int argc, _TCHAR* argv[]) 5 { 6 7 //第一种方法 8 int i,j,k,a[5]; 9 int Sum,Max; 10 Max = a[0]; 11 printf("请输入5个整数：\n"); 12 for(k=0;k<5;k++) 13 { 14 scanf("%d",&a[k]); 15 } 16 17 for(i=0;i<5;i++) 18 { 19 Sum = 0; 20 21 for(j=i;j<5;j++) 22 { 23 Sum =Sum+ a[j]; 24 if(Sum > Max) 25 Max =Sum; 26 } 27 } 28 printf("最大连续子数组的和为：%d\n",Max); 29
//第二种方法 int i,j,a[5]; printf("请输入5个整数：\n"); for(j=0;j<5;j++) { scanf("%d",&a[j]); } int Max = 0; int Sum = 0; for(i=0;i<5;i++) { Sum =Sum + a[i]; if(Sum > Max) Max = Sum; 3 if(Sum < 0) //如果和小于0，则从下个元素重新开始累加 Sum = 0; } printf("最大连续子数组的和为：%d\n",Max);*/ return 0; }
测试数据：
-3 -6 -1 -8 -7（全为负数）
5 3 -9 0 9 （数组中有正数、负数、0）
6 9 -5 1 6 （数组中有正有负，但最大子数组不包含负数）
4 -2 3 -6 8 （此最大子数组包括负数）
四、心得体会：
因为胡亚宝基础比我好，所以她主要负责在确定方法后进行代码编程，我则主要负责代码的测试。但思路都是靠两个人共同的探讨才出现的。我和胡亚宝一起合作发现她有好多优点值得我学习，她比较爱动手，有什么想法都爱在纸上画画，本上敲敲。我老是闷头想，这是不对的。但是两个人一起合作，互相补充。整个进程都很轻松，愉快。
在测试时，胡亚宝的代码正确完整。我们采用了上节课老师教的方法进行测试。第一组全是负数；第二组只有一个负数，负数在最中间；第三组则正负相间。三组测试结果和预测的结果一致。
两人合照：
