最大子段和（分治法+动态规划法）_分治求数列的最大子段和

求最大子段和

此类问题通常是求数列中连续子段和的最大值，经典的股票问题就是考察的这个思想及拓展。
例题：
AcWing:1054. 股票买卖
Leetcode:53. 最大子数组和

分治法O(nlogn)

此类问题时分适合采用分治思想，因为所有子区间$[start,end]$只可能有以下三种可能：

1. 在$[1,\frac{n}{2}]$这个区域内。
2. 在$[\frac{n}{2}+1,n]$这个区域内。
3. 左边界位于$[1,\frac{n}{2}]$，右边界位于$[\frac{n}{2}+1,n]$内。
   

这三种情况的最大值即为所求。前两种情况符合子问题递归特性，可以通过递归求出。

在第三种情况中$\frac{n}{2},\frac{n}{2}+1$必然包含在内，因此可以利用第二种穷举的思路分别向左右扩张求出。

int maxx = -INF;
int maxInterval(vector<int> a, int l, int r) {
	if(l == r) {
		return (a[l] > maxx) ? a[l] : maxx;
	}
	int sum_l = 0, sum_r = 0;
	int mid = (l + r) >> 1;
	sum_l = maxInterval(a, l, mid);
	sum_r = maxInterval(a, mid + 1, r);

	int s1 = 0, x = 0;
	for(int i = mid; i >= 0; i -- ) {
		x += a[i];
		if(x > s1) s1 = x;
	}
	int s2 = 0, y = 0;
	for(int i = mid + 1; i <= r; i ++ ) {
		y += a[i];
		if(y > s2) s2 = y;
	}
	maxx = max(sum_l, s1 + s2);
	maxx = max(maxx, sum_r);
	return maxx;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

动态规划思路O(n)

如果我们用常规思路来枚举所有数字，并判断当前数字是否应该加入到最大子段；那么会发现，当前数字的选择与否并不是由前面已经遍历过的数字所决定，而是由其后面的数字来决定，这也就导致了问题的有后效性。

当出现有后效性问题时，我们当前对子问题做出的选择就不一定为最优解，因为会受到后续数据的影响。

后效性问题是动态规划中一个非常重要的概念，在此引用《算法竞赛进阶指南》（李煜东著）中的一段话：

为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做无后效性。换言之，动态规划对状态空间的遍历构成一张有向无环图，遍历就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的状态，图中的边则对应状态之间的转移，转移的选取就是动态规划中的决策。

在此问题中，我们需要换一种思路来避免有后效性问题，我们可以将遍历到的数字看作必选项，然后判断是否要加上前面的和。我们考虑使用dp[i]来表示以a[i]来结尾的子数组的最大子段和，那么我们可以得到状态转移方程为：
$$dp[i]=max(a[i],dp[i-1]+a[i])$$
那么结果即为：$res=max(res,dp[i])$.

int MaxInterval(vector<int> a, int len) {
	vector<int> dp(len);
	int res = -INF;
	dp[0] = a[0];
	for(int i = 1; i < len; i ++ ) {
		dp[i] = max(a[i], dp[i - 1] + a[i]);
		res = max(res, dp[i]);
	}
	return res;
}
1
2
3
4
5
6
7
8
9
10

扫描法O(n)

动态规划思路的一个空间优化版本。

由于只和当前元素前面的最大值有关，因此只需要记录前面最大值即可。

前面的最大值表示前$i-1$个问题的最优解。

int maxInterval(vector<int> v, int len) {
    int res = v[0], mi = min(0, v[0]), sum = v[0];
    for(int i = 1; i < len; i ++ ) {
        sum += v[i];
        res = max(res, sum - mi);
        mi = min(mi, sum);
    }
    return res;
}
1
2
3
4
5
6
7
8
9