结对开发——返回一个整数数组中最大子数组的和（首尾相接版）

一、题目及题目要求

题目:返回一个整数数组中最大子数组的和。
要求：
（1）输入一个整形数组，数组里有正数也有负数。
（2）数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
（3）如果数组A[0]……A[j-1]首尾相邻，允许A[i-1]， …… A[n-1]， A[0]……A[j-1]之和最大。
（4）同时返回最大子数组的位置。

二、设计思路

这次的编程开发是基于上次的返回一个整数数组中最大子数组的和( http://www.cnblogs.com/a1397240667/p/5322471.html），我和我的搭档开始了认真的讨论，再结合课堂上的同学讨论，如何能在一维数组原有的基础上，加上首尾相连这个条件，最后得到的方法大概思想是：遍历数组里面的每一个数将第一个数变为最后一个数，这样又变成了一个新的一维数组，输出每个数组的最大子数组和，然后比较每个输出的和，找出最大的数。

三、代码

 1 /*2016.3.24 weilihua fengyutong*/
 2 #include <iostream>  
 3 #include<ctime>
 4 #define Num 10000
 5 using namespace std;   
 6 int DTGH_Sum(int a[],int n) //动态规划法求子段和函数
 7 {
 8     int sum = 0;
 9     int *b = (int *) malloc(n * sizeof(int));    //动态为数组分配空间
10     b[0] = a[0];
11     for(int i = 1; i < n; i++)
12     {
13         if(b[i-1] > 0)
14             b[i] = b[i - 1] + a[i];
15         else
16             b[i] = a[i];
17     }
18     for(int j = 0; j < n; j++)
19     {
20         if(b[j] > sum)
21             sum = b[j];
22     }
23     delete []b;        //释放内存
24     return sum;
25 }
26 int main()   
27 {   int temp,b; 
28     int sum=0; 
29     int i; 
30     int a1,a2; 
31     int a[Num];
32     int length=0;
33     while (length==NULL||length == 0)//如果数组长度为空或零则请重新输入
34      {
35       cout<<"请输入数组长度：";
36       cin>>length;
37      }
38     cout<<"生成随机序列： "<<endl; 
39     srand((unsigned)time(NULL)); 
40     for(i=0;i<length;i++)//产生随机序列
41     {
42         if(rand()%2==0)
43         {
44             a[i]=rand()%100;
45         }
46         else
47         {
48             a[i]=(-1)*rand()%100;
49         }    
50             cout<<a[i]<<" ";    
51     }
52     cout<<endl;    
53     cout<<"此首尾相连的数组中最大子数组的和有以下几种可能："<<endl; 
54     cout<<"第1种排列方式："<<endl; 
55     for( i=0;i<length;i++) 
56     {
57         cout<<a[i]<<"  ";
58     } 
59     cout<<"最大子数组和为："<<DTGH_Sum(a,length)<<endl; 
60     a1=DTGH_Sum(a,length); 
61     for(b=1;b<length;b++) 
62     { 
63         temp=a[0]; 
64     for(i=1;i<=length;i++) 
65      {   
66         a[i-1]=a[i]; //将第一个数变为最后一个数
67               
68      } 
69        a[length-1]=temp; 
70        cout<<"第"<<b+1<<"种排列方式："<<endl; 
71        for( i=0;i<length;i++) 
72        {
73            cout<<a[i]<<"  ";
74        } 
75        cout<<"最大子数组和为："<<DTGH_Sum(a,length)<<endl; 
76        if(DTGH_Sum(a,length)>=sum) 
77        {
78            sum=DTGH_Sum(a,length);
79        } 
80     }  
81       a2=sum; 
82       cout<<endl; 
83       if(a1>=a2) 
84       {
85           cout<<"综上，最大的子数组和为："<<a1<<endl;
86       } 
87       else
88       {
89           cout<<"综上，最大的子数组和为："<<a2<<endl;
90       }   
91     return 0;   
92 }

四、运行截图

当数组长度为1000时：

五、项目计划日志

日期&&任务	听课	编写程序	阅读相关书籍	网上查找资料	日总计
周一	100		30	30	160
周二		120	30	30	180
周三		30	30	10	70
周四	100	20	30		150
周五		120	30	30	180
周六		45	30	10	85
周日		200	30	10	240
周总计	200	535	180	110	1065

时间记录日志

3/21

日期	开始时间	结束时间	中断时间	净时间	活动	备注
3/21	14：00	15：50	10	100	听课	软件工程上课
	21：04	21: 34	0	30	阅读书籍	《构建之法》
	22：10	22： 40	0	30	网上查找资料
3/22	18:00	18:30	0	30	阅读书籍	《构建之法》
	19：00	21：30	20	120	编写程序	结对开发- 子数组之和
	22: 15	22: 45	0	30	网上查找资料
3/23	19: 25	20： 00	5	30	编写程序	结对开发- 子数组之和
	22：00	22： 30	0	30	阅读书籍	《构建之法》
	22：40	22： 50	0	10	查找资料
3/24	14：00	15: 50	10	100	上课	软件工程上课
	18：26	18： 50	4	20	编写程序	结对开发- 子数组之和
	22:00	22:30	0	30	阅读书籍	《构建之法》
3/25	14: 00	16: 20	20	120	编写程序	结对开发- 子数组之和
	11：23	12： 00	7	30	网上查找资料
	21:00	21:30	0	30	阅读书籍	《构建之法》
3/26	7： 00	7： 30	0	30	阅读书籍	阅读《构建之法》
	10： 00	11： 00	15	45	编写程序	结对开发- 子数组之和
	9: 45	9： 55	0	10	网上查找资料
3/27	8:20	12:00	20	200	编写程序	结对开发- 子数组之和
	21:00	21:10	0	10	网上查找资料
	21:30	22:00	0	30	阅读书籍	《构建之法》

缺陷记录日志

日期	编号	类型	引入阶段	排除阶段	修复时间	备注
3/24	1	20	编码	编译	4	实参与形参类型对应问题
3/24	2	20	编码	编译	1	申请了动态空间未释放
3/25	3	20	编码	编译	7	当数组长度为0时，无法正常跳出
3/27	4	20	编码	编译	20	逻辑有问题，会突然中止
3/27	5	20	编码	编译	1	变量未初始化

同组伙伴博客：http://www.cnblogs.com/qizhonh/

工作照：

结对开发——返回一个整数数组中最大子数组的和 （首尾相接版）

结对开发——返回一个整数数组中最大子数组的和（首尾相接版）