算法设计与分析--求解最大连续子序列和问题（分治法、蛮力法、动态规划法）

一、问题描述

给定有n(n ≥ 1)个整数的序列，求出其中最大连续子序列的和。
例如：序列{-2, 11, -4, 13, -5, -2}的最大连续子序列和为20
序列{-6, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2}的最大连续子序列和为16
规定：一个序列的最大连续子序列和至少是0，如果小于0，其结果为0

二、问题求解（三种方法）

1. 分治法

算法思路：
对于含有n个整数的序列a[0…n - 1]：

1. 若n=1，表示该序列仅含一个元素，若该元素大于0，则返回该元素，否则返回0

2. 若n>1，先求出该序列的中间位置mid=
   ，该序列的最大连续子序列和所在的子序列只可能位于三个位置：
   （1）该子序列完全位于序列的左半部，即a[0…mid]中。采用递归的方法求出其最大连续子序列和，命名为：max_left_sum。

   （2）该子序列完全位于序列的右半部，即a[mid + 1…n - 1]中。采用递归的方法求出其最大连续子序列和，命名为：max_right_sum。

   （3）该子序列跨越中部而占据左右两部分，即a[mid]被包含在该子序列中。求出左半部从a[mid]开始的最大连续子序列和，命名为：max_left_boarder_sum =
   {0 ≤ i ≤ mid}
   ；再求出右半部从a[mid + 1]开始的最大连续子序列和，命名为：max_right_boarder_sum =
   {mid + 1 ≤ j ≤ n - 1}
   。这种情况下序列的最大连续子序列和为：max_left_boarder_sum + max_right_boarder_sum，命名为：max_mid_sum。
   求出三种情况中的最大值(即max_left_sum, max_right_sum, max_mid_sum中的最大值)，即为所求。
   

代码展示：

#include <iostream>
using namespace std;

int max3(int num1, int num2, int num3) {
	if (num1 > num2) {
		num2 = num1;
	}
	return num2 > num3 ? num2 : num3;
}

int max_sub_sum(int a[], int str, int end) {
	if (str == end) {
		if (a[str] < 0) {
			return 0;
		}
		else {
			return a[str];
		}
	}
	else {
		int max_left_sum, max_right_sum;
		int mid = (str + end) / 2;
		max_left_sum = max_sub_sum(a, str, mid);
		max_right_sum = max_sub_sum(a, mid + 1, end);
		
		int max_left_boarder_sum = 0, max_right_boarder_sum = 0;
		int left_boarder_sum = 0, right_boarder_sum = 0;
		for (int i = mid; i >= str; i--) {
			left_boarder_sum += a[i];
			if (left_boarder_sum > max_left_boarder_sum) {
				max_left_boarder_sum = left_boarder_sum;
			}
		}
		for (int i = mid + 1; i <= end; i++) {
			right_boarder_sum += a[i];
			if (right_boarder_sum > max_right_boarder_sum) {
				max_right_boarder_sum = right_boarder_sum;
			}
		}
		int max_mid_sum = max_left_boarder_sum + max_right_boarder_sum;

		return max3(max_left_sum, max_mid_sum, max_right_sum);
	}
}

int main() {
	int a[] = { -2, 11, -4, 13, -5 ,-2 };
	int len = sizeof(a) / sizeof(a[0]);
	int value = max_sub_sum(a, 0, len - 1);
	cout << "最大连续子序列和为：" << value << endl;
	return 0;
}
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

算法分析：
设求解序列a[0…n - 1]最大连续子序列和的执行时间为T(n)。

1. 若n = 1，则T(n) = 1。
2. 若n > 1，则T(n) = 2 * T(n / 2) + O(n)

根据主定理，该算法时间复杂度为O(n*logn)

2. 蛮力法

蛮力法一共包括三种解法：
解法1：
算法思路：
设含有n个整数的序列a[0…n - 1]和其中任何连续子序列a[i…j](i ≤ j，0 ≤ i ≤ n - 1，i ≤ j ≤ n - 1)，求出它的所有元素之和this_sum，并通过比较将最大值存放在max_sum中，最后返回max_sum。
例如：对于a[0…5] = {-2, 11, -4, 13, -5, -2}，求出的a[i…j](i ≤ j)的所有元素和如图所示，其中20是最大值，即最大连续子序列和。

代码展示：

#include <iostream>
using namespace std;
#define INF 9999

int max_sub_sum(int a[], int len) {
	int this_sum = -INF, max_sum = -INF;
	for (int i = 0; i <= len - 1; i++) {
		for (int j = i; j <= len - 1; j++) {
			this_sum = 0;
			for (int k = i; k <= j; k++) {
				this_sum += a[k];
			}
			if (this_sum > max_sum) {
				max_sum = this_sum;
			}
		}
	}
	return max_sum;
}

int main() {
	int a[] = { -2, 11, -4, 13, -5 ,-2 };
	int len = sizeof(a) / sizeof(a[0]);
	int value = max_sub_sum(a, len);
	cout << "最大连续子序列和为：" << value << endl;
	return 0;
}
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

算法分析：
因为算法中使用了三重循环，所以有：

解法2：
算法思路：
改进前面的算法，在求两个相邻子序列之和时他们之间相互关联。例如：设Sum(a[i…j])表示a[i…j]中所有元素的和。Sum(a[0…3]) = a[0] + a[1] + a[2] + a[3]，而Sum(a[0…4]) = a[0] + a[1] + a[2] + a[3] + a[4]，在前者计算出来的情况下求后者只需要在前者的基础上加上a[4]即可，没有必要每次都重复计算，即求Sum(a[i…j])时的递推关系如下：

代码展示：

#include <iostream>
using namespace std;
#define INF 9999

int max_sub_sum(int a[], int len) {
	int this_sum = -INF, max_sum = -INF;
	for (int i = 0; i <= len - 1; i++) {
		this_sum = 0;
		for (int j = i; j <= len - 1; j++) {
			this_sum += a[j];
			if (this_sum > max_sum){
				max_sum = this_sum;
			}
		}
	}
	return max_sum;
}

int main() {
	int a[] = { -2, 11, -4, 13, -5 ,-2 };
	int len = sizeof(a) / sizeof(a[0]);
	int value = max_sub_sum(a, len);
	cout << "最大连续子序列和为：" << value << endl;
	return 0;
}
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

算法分析：
由于算法仅使用了两层循环，时间复杂度如下：
T(n) = O(n^2)

解法3：
算法思路：
进一步改进解法2，从头开始扫描数组a，用this_sum记录当前子序列之和，用max_sum记录最大连续子序列和。若在扫描中遇到负数，当前子序列和this_sum将会减小。若this_sum为负数，则可以放弃该子序列，重新开始下一个子序列的分析，并置this_sum = 0。若this_sum不断增加，则max_sum也不断增加。

代码展示：

#include <iostream>
using namespace std;
#define INF 9999

int max_sub_sum(int a[], int len) {
	int this_sum = 0, max_sum = -INF;
	for (int i = 0; i <= len - 1; i++) {
		this_sum += a[i];
		if (this_sum < 0) {
			this_sum = 0;
		}
		if (this_sum > max_sum) {
			max_sum = this_sum;
		}
	}
	return max_sum;
}

int main() {
	int a[] = { -2, 11, -4, 13, -5 ,-2 };
	int len = sizeof(a) / sizeof(a[0]);
	int value = max_sub_sum(a, len);
	cout << "最大连续子序列和为：" << value << endl;
	return 0;
}
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

算法分析：
由于算法仅使用了一层循环，时间复杂度如下：
T(n) = O(n)

3. 动态规划法

算法思路：
对于含有n个整数的序列a[0…n - 1]，设bj(1 ≤ j ≤ n)表示a[0…j - 1]的前j个元素中包含a[j - 1]的最大连续子序列和，bj-1表示a[0…j - 2]的前j-1个元素中包含a[j - 2]的最大连续子序列和。
显然，当bj-1 > 0时，bj = bj-1 + a[j - 1]；当bj-1 ≤ 0时，放弃前面选取的元素，从a[j - 1]重新开始选取，bj = a[j ]。用一维动态规划数组dp存放b，对应的状态转移方程如下：
dp[0] = 0;
dp[j] = MAX{dp[j - 1] + a[j - 1], a[j - 1]} 1 ≤ j ≤ n
则序列a的最大连续子序列和等于dp[j](1 ≤ j ≤ n)中的最大者。
从中看到，若序列a的最大连续子序列和等于dp[maxj]，在dp中从该位置向前找，值小于或等于0的元素dp[k]，则a序列中从k + 1开始到maxj位置的所有元素恰好构成最大连续子序列。

例如：a序列为{-2, 11, -4, 13, -5, -2}，dp[0] = 0，求其他元素如下：

其中，dp[4] = 20为最大值，向前找到dp[1] ≤ 0，所以由a2 ~ a4的元素即(11, -4, 13)构成最大连续子序列，和为20

代码展示：

#include <iostream>
using namespace std;
#define MAXN 20

int dp[MAXN];

void max_sub_sum(int a[], int len) {
	dp[0] = 0;
	for (int i = 1; i <= len; i++) {
		dp[i] = max(dp[i - 1] + a[i - 1], a[i - 1]);
	}
}

void show_result(int a[], int len) {
	int maxi = 0;
	for (int i = 1; i <= len; i++) {
		if (dp[i] > dp[maxi]) {
			maxi = i;
		}
	}
	int str;
	for (str = maxi; str >= 0; str--) {
		if (dp[str] < 0) {
			break;
		}
	}
	cout << "求解结果" << endl;
	cout << "\t最大连续子序列和：" << dp[maxi] << endl;
	cout << "\t最大连续子序列：";
	for (int i = str + 1; i <= maxi; i++) {
		cout << a[i - 1] << " ";
	}
	cout << endl;
}

int main() {
	int a[] = { -2, 11, -4, 13, -5, -2 };
	int len = sizeof(a) / sizeof(a[0]);
	max_sub_sum(a, len);
	show_result(a, len);
	return 0;
}
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

算法分析：
由于算法仅包含一重循环，时间复杂度为：T(n) = O(n)