918. 环形子数组的最大和

发表于 分类于 阅读次数： Waline： 本文字数： 1.4k 阅读时长 ≈ 5 分钟

考点

  • 环形DP
  • 最大子数组和

思路

1. 问题描述

给定长度为 \(n\) 的整数数组 \(\texttt{nums}\)，数组首尾相接构成一个环。允许选择一个非空的连续子数组（在环上连续，因此可以“跨过末尾回到开头”），求其元素和的最大值。

2. 为什么“不建议拉长成链再 DP”

一种直觉是将数组复制一份，得到长度 \(2n\) 的链： \[ B = \texttt{nums} \;||\; \texttt{nums} \] 然后在链上求“最大子数组和”。但这在环形问题上有一个关键陷阱：

2.1 必须加上“长度不超过 \(n\)”的约束

环形数组中任意合法子数组最多包含 \(n\) 个元素（不能绕圈超过一圈）。而在 \(B\) 上做普通 Kadane/DP：

  • 会允许选择长度 \(>n\) 的子数组（相当于绕了超过一圈）
  • 得到的最大值可能是非法解

因此，若坚持使用 \(B\)，必须显式施加约束： \[ \max \left\{ \sum_{k=l}^{r} B[k] \; \middle| \; 0 \le l \le r < 2n,\; r-l+1 \le n \right\} \] 这会直接带来设计复杂度：

  • 朴素 DP：需要额外维度记录长度，典型为 \(O(n^2)\)，对 \(n \le 3\times 10^4\) 不可行。
  • 前缀和 + 单调队列：可以做到 \(O(n)\)，但实现复杂，且本题存在更直接的等价建模（见下文），无需复制数组。

结论：复制数组并不是错，但若没有“长度 \(\le n\)”约束必错；加入约束后要么变成 \(O(n^2)\) 超时，要么写成更复杂的单调队列版本。而本题存在更简洁的 \(O(n)\) 方案。

3. 关键建模：把“跨环”转化为“排除一段”

环形最大子数组和可以分成两类：

  1. 不跨环：子数组完全在 \([0, n-1]\) 的线性区间内 \(\Rightarrow\) 这就是经典最大子数组和（Kadane）。
  2. 跨环：子数组从末尾接到开头 \(\Rightarrow\) 这种子数组可以视为：从整段数组中“删掉”中间一段连续区间。

3.1 跨环子数组的等价表达

设跨环子数组为环上的一段连续弧。将其在数组上展开，会形如：

  • 取后缀：\(\texttt{nums}[i..n-1]\)
  • 再取前缀：\(\texttt{nums}[0..j]\)

其和为： \[ \sum_{k=i}^{n-1} \texttt{nums}[k] \;+\; \sum_{k=0}^{j} \texttt{nums}[k] \] 令总和： \[ S = \sum_{k=0}^{n-1} \texttt{nums}[k] \] 注意到被没有选中的那一段恰好是中间的连续区间： \[ \texttt{nums}[j+1..i-1] \] 因此跨环子数组和等于： \[ S \;-\; \sum_{k=j+1}^{i-1} \texttt{nums}[k] \] 于是跨环情况下要最大化子数组和，就等价于最小化被删掉的那段连续子数组和： \[ \max_{\text{wrap}} = S - \min_{\text{linear subarray}}(\text{sum}) \]

3.2 最终答案结构

令：

  • \(\text{mx}\) = 线性最大子数组和
  • \(\text{mi}\) = 线性最小子数组和

则候选答案为： \[ \max(\text{mx},\; S - \text{mi}) \] 但要注意一个边界情况：

3.3 “全负数”陷阱：为什么要特判

当数组全为负数时：

  • 线性最大子数组和 \(\text{mx} < 0\)，此时正确答案应该是“最大的那个负数”（即 Kadane 的结果）。
  • 线性最小子数组和 \(\text{mi} = S\)（整段数组就是最小子数组）。
  • 若直接用 \(S-\text{mi}\)，会得到 \(0\)，对应“删掉整段数组、选空集”，但题目要求子数组非空，因此这是非法的。

所以必须特判： \[ \text{若 } \text{mx} < 0,\; \text{答案} = \text{mx};\quad \text{否则答案} = \max(\text{mx}, S-\text{mi}) \]

4. 程序设计思路：一次遍历同时维护最大/最小子数组

本题可以在一次循环中同时做两次 Kadane：

4.1 最大子数组（Kadane）

定义：

  • \(\text{pmx}\)：以当前位置结尾的最大子数组和（previous max ending here）
  • 转移：

\[ \text{pmx} \leftarrow \max(\texttt{nums}[i],\; \text{pmx} + \texttt{nums}[i]) \]

并维护全局最大： \[ \text{mx} \leftarrow \max(\text{mx},\; \text{pmx}) \]

4.2 最小子数组（Kadane 的对偶）

同理：

  • \(\text{pmi}\)：以当前位置结尾的最小子数组和
  • 转移：

\[ \text{pmi} \leftarrow \min(\texttt{nums}[i],\; \text{pmi} + \texttt{nums}[i]) \]

并维护全局最小： \[ \text{mi} \leftarrow \min(\text{mi},\; \text{pmi}) \]

4.3 总和同时累积

\[ S \leftarrow S + \texttt{nums}[i] \]

4.4 复杂度

  • 时间复杂度：\(\;O(n)\)
  • 空间复杂度：\(\;O(1)\)

5. 参考实现（对用户 AC 代码加注释）

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
class Solution {
public:
    static const int maxn = 3e4 + 5; // 该常量在本实现中未使用，可保留或删除

    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();

        // pmx: 以当前位置结尾的“最大子数组和”
        // mx : 到目前为止的“全局最大子数组和”
        int pmx = nums[0], mx = nums[0], cmx;

        // pmi: 以当前位置结尾的“最小子数组和”
        // mi : 到目前为止的“全局最小子数组和”
        int pmi = nums[0], mi = nums[0], cmi;

        // s: 数组总和 S
        int s = nums[0];

        // 从第二个元素开始做 Kadane（最大）与 Kadane（最小）的同步更新
        for (int i = 1; i < nums.size(); ++i) {

            // 最大子数组：要么从 nums[i] 重新开始，要么接在前一段 pmx 后面
            cmx = max(nums[i], pmx + nums[i]);

            // 最小子数组：要么从 nums[i] 重新开始，要么接在前一段 pmi 后面
            cmi = min(nums[i], pmi + nums[i]);

            // 累加总和
            s += nums[i];

            // 更新“以 i 结尾”的状态
            pmx = cmx;
            pmi = cmi;

            // 更新全局最大/最小
            mx = max(mx, cmx);
            mi = min(mi, cmi);
        }

        // 若 mx < 0，说明全负数：环形不会带来收益，且 S - mi 会变成 0（非法空子数组）
        // 否则答案为 max(线性最大, 总和 - 线性最小)
        return mx < 0 ? mx : max(mx, s - mi);
    }
};