最大连续子数组：从暴力到分治

Views: --

给定数组 A[1..n]A[1..n]，寻找非空连续区间 [l,r][l,r]，使

∑i=lrAi\sum_{i=l}^r A_i

最大。这是最大连续子数组问题，也常叫最大子段和。

1. 从股票价格到差分数组

若已知每天价格 P1,…,PnP_1,\ldots,P_n，在第 ii 天买、第 jj 天卖的收益是 Pj−PiP_j-P_i。令

Ak=Pk+1−Pk,A_k=P_{k+1}-P_k,

则

Pj−Pi=∑k=ij−1Ak.P_j-P_i=\sum_{k=i}^{j-1}A_k.

因此“买卖一次获得最大收益”可以转成差分数组的最大连续子数组。

2. 三种直接方法

2.1 枚举区间并逐段求和

有 O(n2)O(n^2) 个区间，每个区间再花 O(n)O(n) 求和，总计 O(n3)O(n^3)。

2.2 前缀和

定义

Si=∑k=1iAk,S_i=\sum_{k=1}^iA_k,

则区间和为 Sr−Sl−1S_r-S_{l-1}。每个区间可 O(1)O(1) 计算，总计 O(n2)O(n^2)。

2.3 维护最小前缀

对每个右端点 rr，最佳左端点对应此前最小的 Sl−1S_{l-1}。单次扫描即可做到 O(n)O(n)。这与后面动态规划版 Kadane 算法本质相同。

本讲重点先用它理解分治。

3. 分治的三种位置

取中点 mm。最优区间只有三种可能：

  1. 完全位于左半区；
  2. 完全位于右半区；
  3. 跨过中点。

前两种递归解决。跨中点区间一定由“以 mm 结尾的最大后缀”和“以 m+1m+1 开始的最大前缀”组成。

4. 如何在线性时间求跨中点答案

bestLeft = -infinity
sum = 0
for i = m down to l:
    sum += A[i]
    bestLeft = max(bestLeft, sum)

bestRight = -infinity
sum = 0
for j = m + 1 to r:
    sum += A[j]
    bestRight = max(bestRight, sum)

cross = bestLeft + bestRight

两次扫描合计 Θ(r−l+1)\Theta(r-l+1)。

5. 完整算法

MaxSubarray(A, l, r):
    if l == r:
        return A[l]
    m = floor((l + r) / 2)
    left = MaxSubarray(A, l, m)
    right = MaxSubarray(A, m + 1, r)
    cross = MaxCrossing(A, l, m, r)
    return max(left, right, cross)

若还要返回区间端点，就让每个返回值同时携带 (sum,l,r)(sum,l,r)。

6. 正确性

任意连续区间相对中点只能属于上述三类，不存在第四种情况。递归分别求出左右半区的最优解；跨中点时，左侧若不是最大后缀，替换成更大的后缀会得到更优区间，矛盾，右侧同理。因此三者取最大就是全局最优。

7. 复杂度

T(n)=2T(n/2)+Θ(n).T(n)=2T(n/2)+\Theta(n).

由主定理得

T(n)=Θ(nlog⁡n).T(n)=\Theta(n\log n).

辅助数组不需要，递归栈为 O(log⁡n)O(\log n)。

8. 全负数的边界

若要求子数组非空，全负数组的答案应是最大单个元素。初始化为 0 会错误地返回空数组。

例如 [−5,−2,−8][-5,-2,-8]：

  • 非空定义：答案是 −2-2；
  • 允许空数组：答案可以是 0。

题目必须先明确采用哪种定义。课件和多数算法教材采用非空子数组。

9. 一个完整例子

对

[13,−3,−25,20,−3,−16,−23,18,20,−7,12,−5,−22,15,−4,7],[13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7],

最优区间是

[18,20,−7,12],[18,20,-7,12],

和为 43。分治法会在某一层把它识别为跨中点区间。

10. 为什么还要学 O(nlog⁡n)O(n\log n) 解法

最大子数组确实存在 O(n)O(n) 算法，但分治版展示了一个可迁移思路：

  • 先枚举最优解相对分界点的位置类型；
  • 递归处理完全落在子问题中的情况；
  • 为跨边界情况设计高效合并。

逆序对、最近点对、平面分治等问题都会重复这个结构。

评论