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

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

算法导论上的分治算法

详见课本：中文 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)\) 难以改进，但跨越中点的最大子数组复杂度 \(\Theta(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)\)。

#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]。

具体来看 这篇博客 吧，很详细。（上面的图也是从这里盗的）

我写的上面那题：

#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\) 复杂度的区间修改。不过非算法竞赛选手大概永远不会需要它。