[算法]连续子数组最大和

[问题描述]

给定一个数组，求其中一段连续的子数组，使其和最大。

[算法及其实现]

据说这是一个面试的经典问题，照例咱们先来分析分析。如果所有数都是非负的，当然整个数组的和就是最大和；所以当数组中存在负数时，这个问题才有意思。（本题考虑整型数，且一切运算结果不超过int的情况）

一切先从暴力开始思考。一个很朴素的思想是，枚举子数组的起始位置、终止位置，再进行加和。所以这是个O(n^3)的算法，实现如下（c++代码）：

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 #define MaxN 120
 5 void Read(int *a, int &n)
 6 {
 7     int i;
 8     printf("请输入一个整数n，表示数组的元素个数。
");
 9     scanf("%d", &n);
10     printf("请输入n个整数，用空白符隔开。
");
11     for(i = 1; i <= n; i++)
12         scanf("%d", &a[i]);
13 }
14 int Get_Max_Sum(int *a, int n) //求a[1...n]的连续子数组最大和 
15 {
16     int i, j, k;
17     int Ret, Sum;
18     Ret = a[1];
19     for(i = 1; i <= n; i++)
20     {
21         for(j = i; j <= n; j++)
22         {
23             Sum = 0;
24             for(k = i; k <= j; k++)
25                 Sum +=a[k];
26             Ret = max(Ret, Sum);
27         }
28     }
29     return Ret;
30 }
31 int main()
32 {
33     int a[MaxN], n;
34     int Ans;
35     Read(a, n);
36     Ans = Get_Max_Sum(a, n);
37     printf("连续子数组最大和 = %d
", Ans);
38     return 0;
39 }

View Code

当然我们是不满意这样的复杂度的，所以思考优化。很容易能想到，当已知起始位置和终止位置之后，在进行加和计算是愚蠢而耗时的（因为重复计算太多），能不能把这个操作优化一下呢？答案是肯定的。有一个非常常用的技术——维护前缀和。对于原数组a[]来说，我们维护一个新的数组sum[]，其中sum[i]=sigma{a[k]}_{k=1...i}，那么a[i]+a[i+1]+……+a[j]=sum[j]-sum[i-1]，这样一个O(n)的操作就变成O(1)的了。整体的复杂度降为O(n^2)。优化后的代码如下（c++代码）：

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 #define MaxN 120
 5 void Read(int *a, int &n)
 6 {
 7     int i;
 8     printf("请输入一个整数n，表示数组的元素个数。
");
 9     scanf("%d", &n);
10     printf("请输入n个整数，用空白符隔开。
");
11     for(i = 1; i <= n; i++)
12         scanf("%d", &a[i]);
13 }
14 int Get_Max_Sum(int *a, int n) //求a[1...n]的连续子数组最大和 
15 {
16     int i, j;
17     int Ret;
18     a[0] = 0;
19     for(i = 2; i <= n; i++)
20         a[i] += a[i - 1]; //这里a[]就变为了维护前缀和的sum[]
21     Ret = a[1];
22     for(i = 1; i <= n; i++)
23         for(j = i; j <= n; j++)
24             Ret = max(Ret, a[j] - a[i - 1]);
25     return Ret;
26 }
27 int main()
28 {
29     int a[MaxN], n;
30     int Ans;
31     Read(a, n);
32     Ans = Get_Max_Sum(a, n);
33     printf("连续子数组最大和 = %d
", Ans);
34     return 0;
35 }

View Code

但从实际考虑，O(n^2)仍然是一个很高的复杂度，我们当然希望复杂度能够更低。从复杂度上来看，比O(n^2)低的一般来说有两个量级，O(n lg n)和O(n)。先思考O(n lg n)的算法，出现对数，基本上跟二分会扯上关系，那么这个问题能否用分治来实现呢？非常幸运，是可以的。

从答案出发思考，最后得到的使和最大的一段连续的子数组，会出现在什么地方呢？将原数组从中间一分为二mid=(left+right)/2，要么答案出现在左侧，要么答案出现在右侧，要么答案横跨中间位置。前两种情况将问题转化为规模更小、本质没变的子问题了，分治的雏形大致明了了；对于后一种情况，我们很容易证明，最大和=mid向左延伸的最大值+(mid+1)向右延伸的最大值，复杂度为O(n)。所以整体复杂度为O(n lg n)。实现如下（c++代码）：

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 #define MaxN 120
 5 void Read(int *a, int &n)
 6 {
 7     int i;
 8     printf("请输入一个整数n，表示数组的元素个数。
");
 9     scanf("%d", &n);
10     printf("请输入n个整数，用空白符隔开。
");
11     for(i = 1; i <= n; i++)
12         scanf("%d", &a[i]);
13 }
14 int Get_Max_Sum(int *a, int L, int R)
15 {
16     int Ret, tmp, mid = L + (R - L) / 2;
17     int Max1, Max2;
18     int i;
19     /*单个点的情况，直接返回*/
20     if(L == R)
21     {
22         Ret = a[L];
23         return Ret;
24     }
25     /*从左侧得到答案*/
26     Ret = Get_Max_Sum(a, L, mid);
27     /*从右侧得到答案*/
28     tmp = Get_Max_Sum(a, mid + 1, R);
29     Ret = max(Ret, tmp);
30     /*横跨mid的情况，实际上是指至少包括a[mid]和a[mid+1]*/
31     //左侧
32     tmp = 0;
33     Max1 = a[mid];
34     for(i = mid; i >= L; i--)
35     {
36         tmp += a[i];
37         Max1 = max(Max1, tmp);
38     }
39     //右侧
40     tmp = 0;
41     Max2 = a[mid + 1];
42     for(i = mid + 1; i <= R; i++)
43     {
44         tmp += a[i];
45         Max2 = max(Max2, tmp);
46     }
47     tmp = Max1 + Max2;
48     Ret = max(Ret, tmp);
49     return Ret;
50 }
51 int main()
52 {
53     int a[MaxN], n;
54     int Ans;
55     Read(a, n);
56     Ans = Get_Max_Sum(a, 1, n);
57     printf("连续子数组最大和 = %d
", Ans);
58     return 0;
59 }

View Code

到现在为止，这样的复杂度已经足够让人感到满意了。（如果说递归的实现让人担心速度或者爆栈，可以尝试手写栈等，这都是实现技术上的问题，这里笔者认为没有必要纠结）

但是人都是贪心的，之前我们说了，还有一种更低的复杂度的量级O(n)，如果能达到这个级别那多好啊。确实，真的有O(n)的算法。（zyy卖了好久的关子w(ﾟДﾟ)w）

在上一种算法中，有一种情况是当前区间的答案来自于横跨中间位置mid的子数组，其答案由mid向左延伸最大值和(mid+1)向右延伸最大值组成。由此得到启发，我们可以从某一个点向左延伸，当然一定会有一个最大值（相当于固定了子数组的末端位置）。乍一看还是一个平方复杂度的算法，实则不然。考虑当前按位置i，从位置i向前延伸得到的最大和保存在sum[i]中，而对于sum[i]的取值，要么将当前元素a[i]跟之前的加在一起为sum[i]=sum[i-1]+a[i]，要么从i位置重新开始一个新的子串，即sum[i]=a[i]。sum[i]取何值与sum[i-1]有关，若sum[i-1]<0，显然应该丢掉前面的东西重新开始，否则选后者。所以最终答案是max{sum[1...n]}。

具体实现时，我们发现sum[]的元素不会重复使用，故只用一个变量就可以了，另外用一个变量来记录出现过的最大值即可。实现如下（c++代码）：

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 #define MaxN 120
 5 void Read(int *a, int &n)
 6 {
 7     int i;
 8     printf("请输入一个整数n，表示数组的元素个数。
");
 9     scanf("%d", &n);
10     printf("请输入n个整数，用空白符隔开。
");
11     for(i = 1; i <= n; i++)
12         scanf("%d", &a[i]);
13 }
14 int Get_Max_Sum(int *a, int L, int R)
15 {
16     int Sum, Ret, i;
17     Ret = Sum = a[L];
18     for(i = L + 1; i <= R; i++)
19     {
20         if(Sum > 0)
21             Sum += a[i];
22         else
23             Sum = a[i];
24         Ret = max(Ret, Sum);
25     }
26     return Ret;
27 }
28 int main()
29 {
30     int a[MaxN], n;
31     int Ans;
32     Read(a, n);
33     Ans = Get_Max_Sum(a, 1, n); //求数组a[1...n]的子数组最大和
34     printf("%d
", Ans);
35     return 0;
36 }

View Code

这个算法确实应该算作DP，给出状态转移方程：

sum[0] = 0

sum[i] = max{sum[i - 1], sum[i - 1] + a[i]}

Ans = max{sum[i]}_{i=1...n}