算法复习——动态规划篇之最大子数组问题
以下内容主要参考中国大学MOOC
《算法设计与分析》
，墙裂推荐希望入门算法的童鞋学习！
1. 问题背景
子数组
：数组中
连续
的一段序列，例如
X
[
3..7
]
X[3..7]
X
[
3
.
.
7
]
；
子数组和
：子数组中元素的求和，
X
[
3..7
]
X[3..7]
X
[
3
.
.
7
]
的和就是
3
+
5
−
4
+
3
+
2
=
9
3+5-4+3+2=9
3
+
5
−
4
+
3
+
2
=
9
；
那么，问题就是如何寻找数组
X
X
X
中最大的非空子数组？
2. 问题定义
最大子数组问题（Max Continuous Subarray）
输入：
-
给定一个数组
X[
1..
n
]
X[1..n]
X
[
1
.
.
n
]
，对于任意一对数组下标为
l,
r
(
l
≤
r
)
l, r(l \leq r)
l
,
r
(
l
≤
r
)
的非空子数组，其和记为
S(
l
,
r
)
=
∑
i
=
l
r
X
[
i
]
S(l, r)=\sum_{i=l}^{r}X[i]
S
(
l
,
r
)
=
∑
i
=
l
r
X
[
i
]
输出：
-
求出
S(
l
,
r
)
S(l, r)
S
(
l
,
r
)
的最大值，记为
Sm
a
x
S_{max}
S
m
a
x
3. 枚举过程分析
如果使用暴力枚举的话，需要两层枚举：
-
第一层：枚举位置
ii
i
作为区间开头； -
第二层：枚举位置
jj
j
作为区间结尾。
如果想要降低时间复杂度，就需要从两层枚举中舍弃掉一层。
我们可以定义一个记号
D
i
D_{i}
D
i
，表示以
X
[
i
]
X[i]
X
[
i
]
开头的最大子数组，因此只要枚举出所有的
D
i
D_{i}
D
i
，就得到了最大子数组。先看一个案例。
4. 规律
4.1 规律观察
-
结尾位置相同
-
D1
D_{1}
D
1
,
D2
D_{2}
D
2
,
D3
D_{3}
D
3
-
D2
=
X
[
2
]
+
D
1
D_{2}=X[2]+D_{1}
D
2
=
X
[
2
]
+
D
1
-
D1
=
X
[
1
]
+
D
2
D_{1}=X[1]+D_{2}
D
1
=
X
[
1
]
+
D
2
-
-
-
结尾位置不同
-
D3
,
D
4
D_{3}, D_{4}
D
3
,
D
4
-
D3
=
X
[
3
]
D_{3}=X[3]
D
3
=
X
[
3
]
-
D4
<
0
D_{4} < 0
D
4
<
0
-
按照结尾位置相同的规律，
D3
D_{3}
D
3
应该等于
X[
3
]
X[3]
X
[
3
]
加
D4
D_{4}
D
4
，但是
D4
D_{4}
D
4
小于0，还不如直接等于
X[
3
]
X[3]
X
[
3
]
效果好
-
-
4.2 规律描述
设
D
i
D_{i}
D
i
为以
X
[
i
]
X[i]
X
[
i
]
开头的最大子数组和。
-
情况1：设
Di
+
1
>
0
D_{i+1} > 0
D
i
+
1
>
0
时，
Di
=
X
[
i
]
+
D
i
+
1
D_{i}=X[i]+D_{i+1}
D
i
=
X
[
i
]
+
D
i
+
1
-
情况2：设
Di
+
1
≤
0
D_{i+1} \leq 0
D
i
+
1
≤
0
时，
Di
=
X
[
i
]
D_{i}=X[i]
D
i
=
X
[
i
]
4.3 规律证明
-
情况1：
-
Di
+
1
D_{i+1}
D
i
+
1
：以
X[
i
+
1
]
X[i+1]
X
[
i
+
1
]
开头的
最大
子数组和（
Di
+
1
>
0
D_{i+1} > 0
D
i
+
1
>
0
） -
Si
+
1
S_{i+1}
S
i
+
1
：以
X[
i
+
1
]
X[i+1]
X
[
i
+
1
]
开头的
任一
子数组和（
Si
+
1
≤
D
i
+
1
S_{i+1} \leq D_{i+1}
S
i
+
1
≤
D
i
+
1
） -
显然
X[
i
]
+
D
i
+
1
≥
X
[
i
]
+
S
i
+
1
X[i]+D_{i+1} \geq X[i]+S_{i+1}
X
[
i
]
+
D
i
+
1
≥
X
[
i
]
+
S
i
+
1
，因此
Di
=
X
[
i
]
+
D
i
+
1
D_{i}=X[i]+D_{i+1}
D
i
=
X
[
i
]
+
D
i
+
1
- 所以第一种情况成立
-
-
情况2：
-
Di
+
1
D_{i+1}
D
i
+
1
：以
X[
i
+
1
]
X[i+1]
X
[
i
+
1
]
开头的
最大
子数组和（
Di
+
1
≤
0
D_{i+1} \leq 0
D
i
+
1
≤
0
） -
Si
+
1
S_{i+1}
S
i
+
1
：以
X[
i
+
1
]
X[i+1]
X
[
i
+
1
]
开头的
任一
子数组和（
Si
+
1
≤
D
i
+
1
S_{i+1} \leq D_{i+1}
S
i
+
1
≤
D
i
+
1
） -
显然
X[
i
]
+
S
i
+
1
≤
X
[
i
]
+
D
i
+
1
≤
X
[
i
]
X[i]+S_{i+1} \leq X[i]+D_{i+1} \leq X[i]
X
[
i
]
+
S
i
+
1
≤
X
[
i
]
+
D
i
+
1
≤
X
[
i
]
，因此
Di
=
X
[
i
]
D_{i}=X[i]
D
i
=
X
[
i
]
- 所以第二种情况成立
-
5. 动态规划
5.1 问题结构分析
-
给出问题表示：
-
D[
i
]
D[i]
D
[
i
]
：以
X[
i
]
X[i]
X
[
i
]
开头的最大子数组和
-
-
明确原始问题
-
Sm
a
x
=
m
a
x
1
≤
i
≤
n
{
D
[
i
]
}
S_{max}=max_{1 \leq i \leq n}\{D[i]\}
S
m
a
x
=
m
a
x
1
≤
i
≤
n
{
D
[
i
]
}
-
5.2 递推关系建立
5.2.1 分析最优（子）结构
-
D[
i
]
D[i]
D
[
i
]
：以
X[
i
]
X[i]
X
[
i
]
开头的最大子数组和 -
情况1：当
D[
i
+
1
]
>
0
D[i+1]>0
D
[
i
+
1
]
>
0
时，
D[
i
]
=
X
[
i
]
+
D
[
i
+
1
]
D[i]=X[i]+D[i+1]
D
[
i
]
=
X
[
i
]
+
D
[
i
+
1
]
-
情况2：当
D[
i
+
1
]
≤
0
D[i+1] \leq 0
D
[
i
+
1
]
≤
0
时，
D[
i
]
=
X
[
i
]
D[i]=X[i]
D
[
i
]
=
X
[
i
]
-
分析递推关系，我们可以发现在情况一中，
D[
i
]
D[i]
D
[
i
]
是依赖于
D[
i
+
1
]
D[i+1]
D
[
i
+
1
]
的，
D[
i
]
D[i]
D
[
i
]
和
D[
i
+
1
]
D[i+1]
D
[
i
+
1
]
都是最大数组和，只不过
D[
i
+
1
]
D[i+1]
D
[
i
+
1
]
的规模比
D[
i
]
D[i]
D
[
i
]
小，所以大规模问题的最优解是依赖于小规模问题的最优解的，这就满足了动态规划
最优子结构
的性质。
5.2.2 构造递推公式
D
[
i
]
=
{
X
[
i
]
+
D
[
i
+
1
]
,
i
f
D
[
i
+
1
]
>
0
X
[
i
]
,
i
f
D
[
i
+
1
]
≤
0
D[i]=\left\{ \begin{array}{rcl} X[i]+D[i+1], & & {if\ D[i+1] > 0}\\ X[i], & & {if\ D[i+1] \leq 0}\\ \end{array} \right.
D
[
i
]
=
{
X
[
i
]
+
D
[
i
+
1
]
,
X
[
i
]
,
i
f
D
[
i
+
1
]
>
0
i
f
D
[
i
+
1
]
≤
0
5.3 自底向上计算
-
初始化：
D[
n
]
=
X
[
n
]
D[n]=X[n]
D
[
n
]
=
X
[
n
]
-
递推公式：
D[
i
]
=
{
X
[
i
]
+
D
[
i
+
1
]
,
i
f
D
[
i
+
1
]
>
0
X
[
i
]
,
i
f
D
[
i
+
1
]
≤
0
D[i]=\left\{ \begin{array}{rcl} X[i]+D[i+1], & & {if\ D[i+1] > 0}\\ X[i], & & {if\ D[i+1] \leq 0}\\ \end{array} \right.
D
[
i
]
=
{
X
[
i
]
+
D
[
i
+
1
]
,
X
[
i
]
,
i
f
D
[
i
+
1
]
>
0
i
f
D
[
i
+
1
]
≤
0
5.4 最优方案追踪
5.4.1 记录决策过程
-
构造追踪数组
Re
c
[
1..
n
]
Rec[1..n]
R
e
c
[
1
.
.
n
]
，
Re
c
[
i
]
Rec[i]
R
e
c
[
i
]
记录以
X[
i
]
X[i]
X
[
i
]
开头的最大子数组的结尾是第几位-
情况1：结尾相同
-
Re
c
[
i
]
=
R
e
c
[
i
+
1
]
Rec[i]=Rec[i+1]
R
e
c
[
i
]
=
R
e
c
[
i
+
1
]
-
-
情况2：结尾不同
-
Re
c
[
i
]
=
i
Rec[i]=i
R
e
c
[
i
]
=
i
-
-
情况1：结尾相同
5.4.2 输出最优方案
- 从子问题中查找最优解
-
最大子数组开头位置
ii
i
，结尾位置
Re
c
[
i
]
Rec[i]
R
e
c
[
i
]
6. 伪代码
Max-Continuous-Subarray-DP(X, n)
输入：数组X，数组长度n
输出：最大子数组和S_max，子数组起止位置l，r
// 初始化
D[n] ← X[n]
Rec[n] ← n
// 动态规划
for i ← n-1 to 1 do
if D[i+1] > 0 then
D[i] ← X[i] + D[i+1]
Rec[i] ← Rec[i+1]
end
else
D[i] ← X[i]
Rec[i] ← i
end
end
// 查找解
S_max ← D[1]
for i ← 2 to n do
if S_max < D[i] then
S_max ← D[i]
l ← i
r ← Rec[i]
end
end
return S_max, l, r
该算法的时间复杂度是
O
(
n
)
O(n)
O
(
n
)
。