最大子段和的分治算法_最大子段和分治

问题描述

给定由 n 个整数（可能为负整数）组成的序列，求解其连续的最大字段和。当所有数都是负整数时，最大字段和是 0 .
如：a[] = {-2, 11, -4, 13, -5, -2}时， max = 11 + (-4) + 13 = 20.

分治算法思想

将所给序列a[1:n] 分成a[1:n/2] 和 a[n/2 + 1 : n]两个部分，则最大值有一下三种情况：

1. 整个序列的字段和与左半部分相同
2. 整个序列的子段和与右半部分相同
3. 整个序列的子段和 在两个部分的中间连接部分

对应前两种情况利用递归可以直接求出，而第三种情况可以从中间部分向两边蔓延（直到找到的数是负数为止）
时间复杂度为：nlogn

算法实现

int maxSubSum(int *a, int left, int right) {
	if (left == right) {
		return a[left] < 0 ? 0 : a[left];
	}
	    int centor = (left + right) / 2;
    int leftSum = maxSubSum(a, left, centor);
    int rightSum = maxSubSum(a, centor + 1, right);
    int s1 = 0;
    int lefts =0;
    for (int i = centor; i >= left; i--) { // 从中点向左找最大字段和
        lefts += a[i];
        if (lefts > s1) {
            s1 = lefts;
        }
    }
    int s2 = 0;
    int rights = 0;
    for (int i = centor + 1; i <= right; i++) {//从中点向右找最大字段和
        rights += a[i];
        if (rights > s1) {
            s1 = rights;
        }
    }
    int sum = s0 + s1; // 第三种情况的最大子段和
    sum = max(sum, leftSum); // 求解三种情况的最大值
    sum = max(sum, rightSum);
    return sum;
}
int maxSum(int *a, int n) {
	return sumSubSum(a, 1, n); // 可以根据数组a自行调整
}

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

动态规划算法解决

用一个数组b[]，b[j]表示以从位置 j 开始向前找一段的最大子段和，当b[j - 1] > 0时， b[j] = b[j-1] + a[j] , 当 b[j-1] 小于0的时候，b[j] = a[j]，即动态方程为b[j] = max( b[j - 1] + a[j], a[j]). 最后结果为 数组b的最大值
算法实现：

int maxSum(int *a, n) {
	int sum = 0, b = 0;
	for (int i = 0; i < n; i++) {
		if (b > 0) {
			b += a[i]
		} else {
			b = a[i];
		}
		if (b > sum) {
			sum = b; // 存储之前计算的最大值
		}
	}
	return sum;	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14