最大连续子序列和问题

发表于 | 分类于

问题描述

给定整数序列$A_1,A_2,A_3…A_N$，求$\sum_{k=i}^jA_k$的最大值（约定如果所有整数均为负数则最大和为0）。最大子序列和问题既是根据给出的数列抽取某段连续子数列使其和为最大。《数据结构与算法分析：C语言描述》一书中给出了四种解法，以下分别分析实现。

穷举法

穷举法的含义是求出所有子序列的和然后比较得出最大的连续子序列和。对于一个序列字串数量$C_n^2+n+1=n(n+1)/2+1$，其中$C_n^2$是子序列元素数量大于等于2的子序列个数，$n$为元素数量为1得子序列个数，1为空子序列。故穷举法需要计算$O(N^2)$数量的子序列和，而每个子序列需要遍历其中所有的元素进行累加，因此不难推算出穷举法的时间复杂度为$O(N^3)$。以下为穷举法实现的C++算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <vector>
#include <numeric>
using std::vector;

int BruteAlgorithm(const vector<int> &inArray)
{
        int maxSum = 0;
        for (size_t i = 0; i < inArray.size(); i++) {
                for (size_t j = i; j < inArray.size(); j++) {
                        int tmpSum = accumulate(inArray.begin() + i, inArray.begin() + j + 1, 0);
                        maxSum = maxSum > tmpSum ? maxSum : tmpSum;
                }
        }
        return maxSum;
}

穷举法优化

通过观察穷举法最内层代码我们知道accumulate函数每次均从下标i开始累加，前面计算得到的结果完全没有利用到，如果保存上一步计算得到的结果便可以有效地降低时间复杂度，实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <vector>
#include <numeric>
using std::vector;

int BruteOptimize(const vector<int> &inArray)
{
        int maxSum = 0;
        for (size_t i = 0; i < inArray.size(); i++) {
                int tmpSum = 0;
                for (size_t j = i; j < inArray.size(); j++) {
                        tmpSum += inArray[j];
                        maxSum = maxSum > tmpSum ? maxSum : tmpSum;
                }
        }
        return maxSum;
}

上述代码直接把时间复杂度降低到$O(N^2)$

分治递归解法

按照教材的解法，其基本思想是将序列二分，最大连续子序列和只会出现在三个位置：左半边、右半边以及中间位置，因此可以通过分治法计算子序列和，递归终止条件是待计算序列中只含有一个元素。具体实现代码如下：

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
/*start指向第一个元素，end指向最后一个元素的下一个元素*/
int DivideConquerCore(const vector<int> &inArray, int start, int end)
{
        if (end - start <= 1) {
                return inArray[start] > 0 ? inArray[start] : 0;
        }
        int middle = start + (end-start)/2;
        int maxLeftSum = DivideConquerCore(inArray, start, middle);
        int maxRightSum = DivideConquerCore(inArray, middle, end);

        int tmpSum = 0;

        int centerLeftSum = 0;
        for (int i = middle - 1; i >= start; i--) {
                tmpSum += inArray[i];
                centerLeftSum = centerLeftSum > tmpSum ? centerLeftSum : tmpSum;
        }

        tmpSum = 0;
        int centerRightSum = 0;
        for (int i = middle; i < end; i++) {
                tmpSum += inArray[i];
                centerRightSum = centerRightSum > tmpSum ? centerRightSum : tmpSum;
        }

        int centerSum = centerLeftSum + centerRightSum;

        int maxSum = maxLeftSum > maxRightSum ? maxLeftSum : maxRightSum;
        maxSum = maxSum > centerSum ? maxSum : centerSum;
        return maxSum;
}

int DCAlgorithm(const vector<int> &inArray)
{
        return DivideConquerCore(inArray, 0, int(inArray.size()));
}

上述算法时间复杂度递推式为$T(N)=2T(N/2)+N$易得出时间复杂度为$O(N\log(N))$

动态规划解法

动态规划是前人在优化暴力穷举法中通过观察找到优化规律而得出的一种优化思路。前人观察到暴力求解中有大量的重复计算，如果可以减少这些重复计算便可以提高算法性能。考虑到连续子序列问题的连续性特点，我们在扫描数组时维持一个连续子序列，然后考察当前扫描的元素能否加入该子序列或者另起一个新序列。如果当前维持的子序列和加上当前扫描的元素总和大于该元素，则该元素加入该序列中，否则另起新序列（保证下一个元素可以加入序列），同时记录当前序列的和，该元素成为新序列的第一个元素。将上述思路以通过循环不变式的方式证明如下：

  1. 初始化：扫描数组第一个元素加入到维持的序列中即$[a_0]$，此时记录的一个连续子序列和为$S_0$；
  2. 保持：判断当前扫描元素与保持序列和关系，导致两种情况：$[a_0,a_1]$和$[a_1]$，和记为$S_1$。无论那种情况，在扫描下一个元素时我们依旧可以保证当前维持的序列可以和下一个元素合并（保证连续性）且是最好的序列；
  3. 终止：记录了$N$个$S_i$值，找出最大值作为结果返回。

上述思路的代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <vector>
using std::vector;

int DPAlgorithm(const vector<int> &inArray)
{
        vector<int> SArray(inArray.size(), 0);
        SArray[0] = inArray[0];
        for (size_t i = 1; i < inArray.size(); i++) {
                if (SArray[i-1] + inArray[i] < inArray[i]) {
                        /*更换序列*/
                        SArray[i] = inArray[i];
                }
                else {
                        SArray[i] = SArray[i-1]+inArray[i];
                }
        }
        int maxSum = 0;
        for (size_t i = 0; i < SArray.size(); i++) {
                maxSum = maxSum > SArray[i] ? maxSum : SArray[i];
        }
        return maxSum;
}

动态规划优化

通过观察上述代码，我们已经把时间复杂度优化到了$O(N)$了，但是使用了$O(N)$的空间，这是因为我们保存了维持序列过程中产生的所有和，但是代码中下一个和只与上一个和以及当前扫描元素有关，因此我们只保存上一个和以及不断更新最大和值，代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <vector>
using std::vector;

int DPOptimize(const vector<int> &inArray)
{
        int maxSum = 0;
        int lastSum = inArray[0];
        for (size_t i = 1; i < inArray.size(); i++) {
                maxSum = maxSum > lastSum ? maxSum : lastSum;
                if (lastSum + inArray[i] < inArray[i]) {
                        /*更换序列*/
                        lastSum = inArray[i];
                }
                else {
                        lastSum = lastSum+inArray[i];
                }
        }
        return maxSum;
}

算法测试

上述算法的测试代码如下，随机生成一段数列，然后调用每个函数进行测试，为了测试代码正确性，我们直接抄录书上的代码作为测试基准，教材实现代码如下MaxSubsequenceSum函数所示

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
#include <vector>
#include <random>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <chrono>
#include <functional>
using namespace std;
using namespace chrono;

int MaxSubsequenceSum(const int A[], int N)
{
        int ThisSum, MaxSum, j;
        ThisSum = MaxSum = 0;
        for (j = 0; j < N; j++) {
                ThisSum += A[j];
                if (ThisSum > MaxSum) {
                        MaxSum = ThisSum;
                }
                else if (ThisSum < 0) {
                        ThisSum = 0;
                }
        }
        return MaxSum;
}

int main()
{
	const int testNum[] = { 10, 100, 1000, 10000, 100000, 1000000, 10000000 };

	default_random_engine randEngine(unsigned(time(nullptr)));
	uniform_int_distribution<int> intDis(int(-10e4), int(10e4));

        int testTimes = 5;

	while ((testTimes--) > 0) {
                for (size_t i = 0; i < sizeof(testNum) / sizeof(testNum[0]); i++) {
                        vector<int> testData1;
                        int *testData2 = new int[testNum[i]];

                        for (int j = 0; j < testNum[i]; j++) {
                                int tmp = intDis(randEngine);
                                testData1.push_back(tmp);
                                testData2[j] = tmp;
                        }

                        auto startTime = system_clock::now();

                        int maxSum = -1;
                        //maxSum = DPOptimize(testData1); /*调用具体的算法*/

                        auto endTime = system_clock::now();

                        int correctSum = MaxSubsequenceSum(testData2, int(testNum[i]));

                        cout << ((maxSum == correctSum) ? "Correct;" : "Wrong;");

                        auto duration = duration_cast<microseconds>(endTime - startTime);
                        cout << "TimeCost:" << duration.count() << endl;
                        delete [] testData2;
                }
        }
	return 0;
}

参考文章

数据结构与算法分析