数组之求最大子数组之和（二）

相比第一次这次数组改编为环形数组所以最大子数组可以分情况讨论

1.和最大子数组没有跨过数组首尾

　　　此时可以使用上一个程序的方法

2.和最大子数组跨过数组首尾

　　　此时选择数组总和-最小子数组和得到最大子数组和

最后再将两者进行比较确定最大的子数组之和

代码如下

 1 //可以分两个情况
 2 //1.和最大子数组没有跨过数组首尾
 3 //    此时可以使用上一个程序的方法
 4 //2.和最大子数组跨过数组首尾
 5 //    此时选择 数组总和-最小子数组和得到最大子数组和
 6 //最后通过比较两个和的大小选择实际和大小
 7 
 8 #include<iostream>
 9 using namespace std;
10 int main()
11 {
12     int i,num,Max2Sum,result;
13     cout << "请输入数组元素个数： " ;
14     cin >> num;
15     int *arr = new int[num];
16     cout << "请依次输入数组元素" << endl;
17     for (i = 0; i < num; i++)
18     {
19         cin >> arr[i];
20     }
21     int Sum=0;
22     int temp=0 ;
23     int CurSum=0;
24     int MaxSum=0;
25     int MinSum=0;
26     for (i = 0; i<num; i++)
27     {
28         //第二种情况，求得最大值为Sum-MinSum
29         Sum+=arr[i];
30         if (temp>0)
31         {
32             temp=arr[i];
33         }
34         else
35         {
36             temp=temp+arr[i];
37         }
38         if (temp<MinSum)
39         {
40             MinSum=temp;
41         }
42         //第一种情况，求得最大值为CurSum
43         CurSum+=arr[i];
44         if(CurSum>MaxSum)
45         {
46             MaxSum=CurSum;
47         }
48         if(CurSum<0)
49         {
50             CurSum=0;
51         }
52     }
53     Max2Sum=Sum-MinSum;
54     if(CurSum>Max2Sum)  //较大的为最大值
55     {
56         result=CurSum;
57     }
58     else
59     {
60         result=Max2Sum;
61     }
62     cout <<"该数组中最大子数组的和是： "<< result<<endl;
63     system("pause");
64     return 0;
65 }

第二种

周活动日志：

	听课	编写程序	阅读课本	日总计
周一	2h		0	2h
周二	0		0	0
周三	0		1h	1h
周四	0	2h	0	0
周五	0	1h	0	1h
周六	0	3h	0	3h
周日
周总计	200	6h	1	6h

缺陷日志：

日期

编号

缺陷内容

引入阶段

排除阶段

修复时间

修复缺陷

3月25日

时间复杂度的最优化

编写代码

思考、查资料

1h+

动态规划

3月26日

如何计算循环

数组首尾相接处

连续子段的和

编写代码

思考、查资料

120+

数组总和减去最小子数组组