求最大子段和
此类问题通常是求数列中连续子段和的最大值,经典的股票问题就是考察的这个思想及拓展。
例题:
AcWing:1054. 股票买卖
Leetcode:53. 最大子数组和
分治法O(nlogn)
此类问题时分适合采用分治思想,因为所有子区间 [ s t a r t , e n d ] [start, end] [start,end]只可能有以下三种可能:
- 在 [ 1 , n 2 ] [1,\frac{n}{2}] [1,2n]这个区域内。
- 在 [ n 2 + 1 , n ] [\frac{n}{2}+1, n] [2n+1,n]这个区域内。
- 左边界位于
[
1
,
n
2
]
[1,\frac{n}{2}]
[1,2n],右边界位于
[
n
2
+
1
,
n
]
[\frac{n}{2}+1 ,n]
[2n+1,n]内。
这三种情况的最大值即为所求。前两种情况符合子问题递归特性,可以通过递归求出。
在第三种情况中 n 2 , n 2 + 1 \frac{n}{2},\frac{n}{2}+1 2n,2n+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
]
=
m
a
x
(
a
[
i
]
,
d
p
[
i
−
1
]
+
a
[
i
]
)
dp[i] = max(a[i], dp[i - 1] + a[i])
dp[i]=max(a[i],dp[i−1]+a[i])
那么结果即为:
r
e
s
=
m
a
x
(
r
e
s
,
d
p
[
i
]
)
res=max(res, dp[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;
}
扫描法O(n)
动态规划思路的一个空间优化版本。
由于只和当前元素前面的最大值有关,因此只需要记录前面最大值即可。
前面的最大值表示前 i − 1 i-1 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;
}