tag: 动态规划、贪心
P1115 最大子段和 – 洛谷
题意
给出一个长度为 n (
1
≤
n
≤
2
∗
10
5
1 \\leq n \\leq 2*10^5
1≤n≤2∗105) 的序列 a (
−
10
4
≤
a
i
≤
10
4
-10^4 \\leq a_i \\leq 10^4
−104≤ai≤104)，选出其中连续且非空的一段使得这段和最大。
题解
注：本题解只讲解了
O
(
n
)
O(n)
O(n)的算法思路，如需
O
(
n
l
o
g
)
O(nlog)
O(nlog)的分治思路可以参考其他题解
思路一
本题目标是找最大子段和，子段由左右两端点唯一确定，故最直接的想法是枚举所有的点对作为左右端点，然后计算区间和、找到最大值，这样最优的时间复杂度是
O
(
n
2
)
O(n^2)
O(n2)，2e5的数据量无法处理。
考虑如何降低时间复杂度，枚举所有左右端点是不可取的，尝试思考是否可以只枚举两端点之一，另一端点的最优位置通过算法来得到。例如固定左端点L，右端点R待定，对于
2
∗
10
5
2*10^5
2∗105的数据量，右端点需快于
O
(
l
o
g
n
)
O(logn)
O(logn)求出。
二分？随着右端点从L处右移，区间和是个多峰的函数，故不能用二分确定。
进一步思考，无论右端点在哪儿，我们只要求出来从L开始的所有前缀和的最大值，就可以知道R取最优位置时的子段和。给定左端点，求前缀和最大值的时间复杂度是
O
(
n
)
O(n)
O(n)，如果不优化依然整体是
O
(
n
2
)
O(n^2)
O(n2)。
但聪明的你会发现：[l,n]的前缀和最大值可以递推出[l-1,n]的前缀最大值（全部多了一个
a
l
−
1
a_{l-1}
al−1，只需要将[l,n]的前缀和最大值加上
a
l
−
1
a_{l-1}
al−1即可，如果[l,n]的前缀和最大值是负数，那么[l-1,n]的前缀和最大值就是
a
l
−
1
a_{l-1}
al−1），这样优化后，整体的时间复杂度可以做到
O
(
n
)
O(n)
O(n)。
思路二
上述通过正常人的思路得到了解法，但如果你曾经接触过动态规划，我们可以换一个讲法：
我们现在的问题是对于n个数字的序列，求最大子段和，首先明确此题是最优性问题，考虑如何定义DP状态。状态要能直接或间接表示出最终结果，如果直接定义
d
p
[
x
]
dp[x]
dp[x]为前
x
x
x个元素组成的序列的最大子段和，会发现无法递推，因为最大子段和可能不包含
a
x
a_x
ax，而子段是连续的，没办法判断
a
x
+
1
a_{x+1}
ax+1对最大子段和的贡献，也就无法确定
d
p
[
x
+
1
]
dp[x+1]
dp[x+1]的值。对于这个问题，我们考虑修改状态，令
d
p
[
x
]
dp[x]
dp[x]指代包含元素
a
x
a_x
ax的最大子段和，这样就可以递推
d
p
[
x
+
1
]
dp[x+1]
dp[x+1]了。
{
d
p
[
x
+
1
]
=
d
p
[
x
]
+
a
x
(
d
p
[
x
]
>
0
)
d
p
[
x
+
1
]
=
a
x
(
d
p
[
x
]
≤
0
)
\\begin{cases} dp[x+1]=dp[x]+a_x &\\quad (dp[x] > 0) \\\\ dp[x+1]=a_x &\\quad (dp[x] \\leq 0) \\end{cases}
{dp[x+1]=dp[x]+axdp[x+1]=ax(dp[x]>0)(dp[x]≤0)
最后只需求dp数组的最大值，就可以得到答案。
总结：实际上两种讲法是同一种代码，只是思考方式不同，读者可以自行感悟。
代码：
代码中的写法进一步优化，不需要前缀和最大值数组或是dp数组作为中介，直接实时维护最大值。
#include <bits/stdc++.h>
using namespace std;
int main(){
/*
n: 序列长度
vec: 读入的序列
ans: 历史最大子段和
now: 包含当前元素的最大子段和
*/
const int INF = 0x7f7f7f7f;
int n;
int ans = –INF, now = 0;
// 读入数据
scanf("%d",&n);
vector<int> vec(n+1);
for(int i = 1;i <= n;i ++) scanf("%d",&vec[i]);
// 遍历一次，直接得出答案
for(int i = 1;i <= n;i ++){
if(now < 0) now = vec[i]; // 小于零前面的就可以不要了
else now += vec[i]; // 大于零可以把前面接到vec[i]的前面
ans = max(ans, now);
}
// 输出答案
printf("%d", ans);
return 0;
}
