Maximum SubArray Problem (最大子数组问题) 分治算法的改进

  1. 算法导论上的分治算法
  2. FIND-MAX-CROSSING-SUBARRAY 太慢辣
  3. 一些解法及其复杂度
  4. 可是 Kadane 好写啊
  5. 线段...树?!
    1. 单点修改
    2. 区间查询
      1. 具体做法:依然是递归
      2. 分析复杂度

最大子数组问题:在数组找到一个连续的子数组,使该子数组的和最大。又称,最大子段和,最大子数列。

算法导论上的分治算法

详见课本:中文 P39,英文 P68。

将 A[low..high] 分成 A[low..mid] 和 A[mid+1..high] 两份递归,并计算跨越中点的的最大子数组,方法为找到形如 A[i..mid] 和 A[mid+1..j] 的最大子数组并合并。

\(T(n) = 2T(n/2)+\Theta(n)\),故复杂度为\(O(n\lg n)\)

FIND-MAX-CROSSING-SUBARRAY 太慢辣

分治的 \(2T(n/2)\) 难以改进,但跨越中点的最大子数组复杂度 \(O(n)\) 可以降低。

发现计算跨越中点的的最大子数组的过程即为计算 A[low..mid] 确定右端点的最大子数组,以及 A[mid+1..high] 确定左端点的最大子数组,可以通过递归解决。

具体算法为:

FIND-MAXIMUM-SUBARRAY(A, low, high) 的返回值包括 sum, maxl, maxr, max。
其中 sum 表示数组 A[low..high] 的和;
maxl 表示左端点从 low 开始的最大子数组;
maxr 表示右端点从 high 开始的最大子数组;
max 表示 A[low..high] 的最大子数组。

通过 L = FIND-MAXIMUM-SUBARRAY(A, low, mid) 和 R = FIND-MAXIMUM-SUBARRAY(A, mid+1, high) 来更新。
sum = L.sum + R.sum;
maxl = max(L.maxl, L.sum + R.maxl);
maxr = max(R.maxr, R.sum + L.maxr);
max = max(L.max, R.max, L.maxr + R.maxl)。

\(T(n) = 2T(n/2)+\Theta(1)\),故复杂度为\(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdio>
struct node {
int sum, maxl, maxr, max;
};
node MaxSubarray(int *a, int l, int r) {
if (l == r) return (node){a[l], a[l], a[l], a[l]};
int mid = l + r >> 1;
node L = MaxSubarray(a, l, mid), R = MaxSubarray(a, mid + 1, r), T;
T.sum = L.sum + R.sum;
T.maxl = std::max(L.maxl, L.sum + R.maxl);
T.maxr = std::max(R.maxr, R.sum + L.maxr);
T.max = std::max(std::max(L.max, R.max), L.maxr + R.maxl);
return T;
}
int main() {
int n, a[10001];
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
printf("%d\n", MaxSubarray(a, 1, n).max);
}

一些解法及其复杂度

  • 暴力 \(O(n^3)\) / \(O(n^2)\)
  • 分治 \(O(n\lg n)\) -> 优化 \(O(n)\)
  • DP / 贪心(Kadane 算法)\(O(n)\)(即习题4.1-5,依次加并保证\(\geq 0\)。详见 WIKI。)

可是 Kadane 好写啊

此分治算法在实现上比 Kadane 算法要复杂得多,但其优势在于可以通过分治思想解决更复杂的问题。

如果问题中的数组发生单点修改(动态数组),那么需要通过线段树操作而达到总时间 \(O(n + Q\lg n)\) 的最优效果,其中 \(Q\) 为修改和询问的次数。

来看个算法题: > 【Vijos 1083 / bzoj 1756】 小白逛公园
输入长度为 n (<= 5e5) 的数组 A。有 m (<= 1e6) 次询问,输入 x, y, z。若 x=1,则求 A[y,z] 或 A[z,y] 之间的最大子段和;若 x=2,则将 A[y] 赋为 z。

以上题目和原题的区别有两点:查询任意区间 & 修改单点的值。

线段...树?!

线段树(Segment Tree)是一种算法竞赛中常用的数据结构。结构是二叉树,每个结点保存一段线段(这里可以理解为区间)。(注:理论科学和竞赛中的算法有一些偏差,在此不做讨论。)

可以理解为,上面的分治算法,在执行过程中,将每次函数执行作为一个结点,保存其函数返回值。

每个结点需要保存的有:左孩子和右孩子的指针、区间(左右端点)、运算相关的值(如上面的 sum 和 max)。

From 刘汝佳 《训练指南》 P199

由二叉树性质,总结点个数为 2n-1。

单点修改

单点修改即修改原数列中的一个位置的值,并维护线段树的性质。

此时,只会有一条链上结点的值发生变化。故时间复杂度为 \(O(\lg n)\)

如下图,修改 [10] 的值,只会递归修改区间 [1,13]、[8,13]、[8,10]、[10] 结点所保存的答案。

此时输出 root 结点的 max 值即为 A[1..n] 的最大子段和。

区间查询

上面一题同时涉及到了区间查询,即区间并非总是 [1..n]。

那么一种做法就是,用 2n-1 个已知区间中的尽量少个来合并出待求区间。
如上图中 [1,10] = [1,7] + [8,10];
[5,11] = [5,7] + [8,10] + [11];
[4,7] = [4] + [5,6] + [7]。

具体做法:依然是递归

以函数 FIND(node, low, high) 查询 [low..high] 为例,若 node 结点表示区间与 [low, high] 相同,则答案已知;否则需要在 node 结点的两个子区间里递归查询,并通过之前的算法(见代码中的 Merge 函数)得到 FIND(node, low, high) 的结果。

即若当前区间与待求相同则直接返回答案;否则继续递归。

分析复杂度

结论:最终处理到的结点不超过 2 lg n 个。即任何查询可以被 2 lg n 个已知区间覆盖。故查询的时间复杂度也是 \(O(\lg n)\)

下图为直观描述。查询区间 [2,12]。从下向上考虑。对于每一层中间的结点,每两个可以向上合并为一个结点,故每一层最多剩下两端的两个结点。最终 [2,12] 可以表示为 [2]+[3,4]+[5,7]+[8,10]+[11,12]。

具体来看 这篇博客 吧,很详细。(上面的图也是从这里盗的)

我写的上面那题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstdio>
const int inf = 0x7fffffff;
struct value {
int sum, maxl, maxr, max;
};
struct node {
int l, r; // 区间 A[l,r]
node *lc, *rc; // 两个孩子
value v; // 值
} *root;
value Merge(value L, value R) { // 和本文第二部分的算法相同
if (L.max == -inf) return R;
if (R.max == -inf) return L;
value T;
T.sum = L.sum + R.sum;
T.maxl = std::max(L.maxl, L.sum + R.maxl);
T.maxr = std::max(R.maxr, R.sum + L.maxr);
T.max = std::max(std::max(L.max, R.max), L.maxr + R.maxl);
return T;
}
void Build(node *x, int l, int r) {
x->l = l, x->r = r;
if (l == r) {
scanf("%d", &x->v.sum);
x->v.maxl = x->v.maxr = x->v.max = x->v.sum;
return;
}
int mid = l + r >> 1;
Build(x->lc = new node, l, mid);
Build(x->rc = new node, mid + 1, r);
x->v = Merge(x->lc->v, x->rc->v);
}
void Change(node *x, int pos, int key) {
if (x->l == x->r) {
x->v = (value){key, key, key, key};
return;
}
Change(pos <= x->l + x->r >> 1 ? x->lc : x->rc, pos, key); // pos<=mid 则递归修改左孩子,否则右孩子
x->v = Merge(x->lc->v, x->rc->v);
}
value Query(node *x, int l, int r) { // Query 过程并不会对 node 中的值做任何修改,函数返回值只和此次询问有关
if (l > r) return (value){-inf, -inf, -inf, -inf}; // 区间为空,在 Merge 中会特判
if (l == x->l && r == x->r) return x->v; // 区间正好为 A[x->l, x->r],答案在 Build 过程中已经算好了
int mid = x->l + x->r >> 1;
return Merge(Query(x->lc, l, std::min(mid, r)), Query(x->rc, std::max(mid + 1, l), r)); // 递归并合并
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
Build(root = new node, 1, n);
for (int x, y, z; m; --m) {
scanf("%d%d%d", &x, &y, &z);
if (x == 1) printf("%d\n", Query(root, std::min(y, z), std::max(y, z)).max);
else Change(root, y, z);
}
}

还可以看 CDOJ 844 的题解(题意是一样的) 或者 另一种代码风格,以及 我高中写的线段树模板

当然线段树在一些性质下还可以支持 lg n 复杂度的区间修改。但是非算法竞赛选手大概永远不会需要它。