最大子段和（分治法+动态规划法）

本文主要是介绍最大子段和（分治法+动态规划法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求最大子段和

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

分治法O(nlogn)

此类问题时分适合采用分治思想，因为所有子区间 $[s t a r t, e n d]$ 只可能有以下三种可能：

在 $[1,\frac{n}{2}]$ 这个区域内。
在 $[\frac{n}{2}+1, n]$ 这个区域内。
左边界位于 $[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;
}

动态规划思路O(n)

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

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

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

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

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

扫描法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;
}