这是一道考的烂的不能再烂的题目，但是依然有很多公司乐于将这样的题目作为笔试或面试题，足见其经典。
问题是这样的：一个整数数组中的元素有正有负，在该数组中找出一个连续子数组，要求该子数组中各元素的和最大，这个子数组便被称作最大子数组。比如数组{2,4,-7,5,2,-1,2,-4,3}的最大子数组为{5,2,-1,2}，最大子数组的和为5+2-1+2=8。
下面按照时间复杂度逐步优化的顺序依次给出这三种算法。
该方法的思想非常简单，先找出从第1个元素开始的最大子数组，而后再从第2个元素开始找出从第2个元素开始的最大子数组，依次类推，比较得出最大的子数组。实现代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
/*常规方法,时间复杂度O（n*n）先从第一个元素开始向后累加，每次累加后与之前的和比较，保留最大值，再从第二个元素开始向后累加，以此类推。*/int MaxSubSum1(int *arr,int len){ int i,j; int MaxSum = 0; //每次开始累加的起始位置的循环 for(i=0;i<len;i++) cursum="" int="" j="i;j<len;j++)"> MaxSum) MaxSum = CurSum; } } return MaxSum;}</len;i++)> |
很明显地可以看出，该方法的时间复杂度为O（n*n）。
考虑将数组从中间分为两个子数组，则最大子数组必然出现在以下三种情况之一：
1、完全位于左边的数组中。
2、完全位于右边的数组中。
3、跨越中点，包含左右数组中靠近中点的部分。
递归将左右子数组再分别分成两个数组，直到子数组中只含有一个元素，退出每层递归前，返回上面三种情况中的最大值。实现代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
/*求三个数中的最大值*/int Max3(int a,int b,int c){ int Max = a; if(b > Max) Max = b; if(c > Max) Max = c; return Max;}/*次优算法，采用分治策略*/int MaxSubSum2(int *arr,int left,int right){ int MaxLeftSum,MaxRightSum; //左右边的最大和 int MaxLeftBorderSum,MaxRightBorderSum; //含中间边界的左右部分最大和 int LeftBorderSum,RightBorderSum; //含中间边界的左右部分当前和 int i,center; //递归到最后的基本情况 if(left == right) if(arr[left]>0) return arr[left]; else return 0; //求含中间边界的左右部分的最大值 center = (left + right)/2; MaxLeftBorderSum = 0; LeftBorderSum = 0; for(i=center;i>=left;i--) { LeftBorderSum += arr[i]; if(LeftBorderSum > MaxLeftBorderSum) MaxLeftBorderSum = LeftBorderSum; } MaxRightBorderSum = 0; RightBorderSum = 0; for(i=center+1;i<=right;i++) { RightBorderSum += arr[i]; if(RightBorderSum > MaxRightBorderSum) MaxRightBorderSum = RightBorderSum; } //递归求左右部分最大值 MaxLeftSum = MaxSubSum2(arr,left,center); MaxRightSum = MaxSubSum2(arr,center+1,right); //返回三者中的最大值 return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum);}/*将分支策略实现的算法封装起来*/int MaxSubSum2_1(int *arr,int len){ return MaxSubSum2(arr,0,len-1);} |
设该算法的时间复杂度为T（n）,则：
T（n）= 2T（n/2）+ O（n），且T（1）= 1。
逐步递推得到时间复杂度T（n）= O（nlogn）。
该算法在每次元素累加和小于0时，从下一个元素重新开始累加。实现代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
/*最优方法，时间复杂度O（n）和最大的子序列的第一个元素肯定是正数因为元素有正有负，因此子序列的最大和一定大于0*/int MaxSubSum3(int *arr,int len){ int i; int MaxSum = 0; int CurSum = 0; for(i=0;i<len;i++) cursum=""> MaxSum) MaxSum = CurSum; //如果累加和出现小于0的情况， //则和最大的子序列肯定不可能包含前面的元素， //这时将累加和置0，从下个元素重新开始累加 if(CurSum < 0) CurSum = 0; } return MaxSum;}</len;i++)> |
显然，该算法的时间复杂度O（n）。该算法理解起来应该不难，但是要想出来可就不容易了。另外，该算法的一个附带的有点是：它只对数据进行一次扫描，一旦元素被读入并被处理，它就不再需要被记忆。因此，如果数组在磁盘或磁带上，他就可以被顺序读入，在主存中不必存储数组的任何部分。不仅如此，在任意时刻，该算法都能对它已经读入的数据给出最大子数组（另外两种算法不具有这种特性）。具有这种特性的算法叫做联机算法。
原文：http://www.cnblogs.com/jerrypp/p/5030725.html