返回一个整数数组中最大子数组的和

要求：

输入一个整型数组，数组里有正数也有负数。

数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

求所有子数组的和的最大值。要求时间复杂度为O(n)。

第一次读题目时，将重点放到了输入一个既有正数也有负数的整型数组上，想着如何随机输入，从而使整个题目难以入手。

再读题目后，将整型数组直接定义完成。题目的重点在于如何去求子数组和的最大值，并且时间复杂度为O（n）。

刚开始思路采用最直接的办法，将所有的数组之和一个一个求出并比较，但这样做，时间复杂度不可能为O(n)。

 1 for (int i = 0; i < n; i++)
 2 {
 3     for (int j = i; j < n; j++)
 4     {
 5         for (int k = i; k < j; k++)
 6         {
 7             b += arr[k];
 8         }
 9         if (b > MaxSum)
10             MaxSum = b;
11                 b = 0;
12     }
13 }
14 return MaxSum;

随后通过网上查找资料，发现这是一道著名的面试题目，通过看大神的代码，得出最简洁的过程：

因为整个数组中有正有负，因此子数组的和也有这两种可能，通过分析，当某一段子数组的和为负数时，就没有继续加下去的必要，将出现负数和之前的那个最大和用b表示出来，而新的子数组从出现负数和最后一位的下一位开始加，因此可以节约不少时间。

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int MaxSum(int *arr, int size)
 5 {
 6     int MaxSum = 0;
 7     int b = 0;//b是子数组的和
 8 
 9     for (int i = 0; i < size; i++)
10     {
11         if (b < 0)
12             b = arr[i];//当子数组和小于0时，与无论与后面数组如何相加，和肯定小于后一段数组之和，此时，将b重新赋值，置为下一个元素
13         else
14             b += arr[i];
15         if (MaxSum < b)
16             MaxSum = b;
17     }
18     return MaxSum;
19 }
20 
21 int main()
22 {
23     int arr[10] = { 2, -3, 4, 1, -6, 2, 10, -1, 9, 5 };
24     cout <<"最大子数组的和为："<< MaxSum(arr, 10) << endl;
25     return 0;
26 }

通过这次练习，发现自己编程能力仍然很欠缺，缺少编程实践，只能通过去查阅资料来获得思路，这次练习自己的完成度也不是很高，有待加强。

时间记录表

日期	开始时间	结束时间	中断时间	净时间	活动	备注
15.3.25	19:00	21:00	10	110	编程	基础教学楼602
	22:00	22:24			看书
15.3.26	16:37	17:30			查阅资料
	18:49	19:45			根据查阅的资料修改程序
	19:51				程序完成	自己的完成度不高

缺陷日志没有及时记录。