1186. 删除一次得到子数组最大和

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

考点

  • 状态机DP
  • 状态设计

思路

目标：给定整数数组 \(a[1..n]\)，选取一个非空连续子数组，并允许在其中最多删除一个元素（也可以不删），求能得到的最大子数组和。

1. 统一下标与符号

把代码里的 arr[i-1] 记为数学下标的 \(a[i]\)。

  • \(n = \text{len}(a)\)
  • 下面所有 DP 下标都是 \(1..n\)；额外引入 \(0\) 号位用于“边界/空前缀”。

2. 状态定义（对应代码的两行 f[0][i] / f[1][i]）

我们维护两类“必须以 \(i\) 结尾”的最优值： \[ \begin{aligned} f_0[i] &: \text{以 } i \text{ 结尾、未删除元素的最大子数组和} \\ f_1[i] &: \text{以 } i \text{ 结尾、在子数组里至多删除一次，且 } a[i] \text{ 保留的最大和} \end{aligned} \] 注意：这里的 \(f_1[i]\) 要求结尾元素 \(a[i]\) 被保留，所以“删除当前 \(a[i]\)”不会落在 \(f_1[i]\) 里，这也是代码里额外比较 f0[i-1] 的原因（后面解释）。

3. 初始值（点阵图解释）

代码：

1
2
3
f[0][0] = 0, f[1][0] = neg;
f[0][1] = f[1][1] = arr[0];
res = arr[0];

数学含义：

  • \(f_0[0]=0\)：只作为边界占位（让 \(i=2\) 时的 \(f_0[i-2]\) 有意义）
  • \(f_1[0] = -\infty\)：表示“不可能”（代码用很小的负数 neg）
  • \(f_0[1]=a[1]\)：只有一个元素，子数组只能选 \([1,1]\)
  • \(f_1[1]=a[1]\)：允许“至多删一次”，但此时也可以选择不删

点阵图 1：初值落点（列是下标 \(i\)，行是状态）

1
2
3
4
5
6
7
          i=0        i=1
        ┌────────┬────────┐
f0 行   │  ● 0    │  ● a1  │
        ├────────┼────────┤
f1 行   │  ● -∞   │  ● a1  │
        └────────┴────────┘
说明：● 表示该格被定义并在后续转移中可被引用

4. 状态转移方程（含精确依赖点阵图）

4.1 不删：标准 Kadane（对应 f[0][i]）

\[ f_0[i] = \max\big(f_0[i-1] + a[i],\ a[i]\big) \]

解释：要么把 \(a[i]\) 接在“以 \(i-1\) 结尾的最优不删子数组”后面；要么从 \(a[i]\) 重新开一段。

4.2 至多删一次且保留 \(a[i]\)（对应 f[1][i]）

代码：

1
f[1][i] = max(f[0][i - 2], f[1][i - 1]) + arr[i - 1];

数学式： \[ f_1[i] = \max\big(f_1[i-1],\ f_0[i-2]\big) + a[i]\qquad(i\ge 2) \] 两种来源：

  1. 删除发生在更早处：从 \(f_1[i-1]\) 延伸，加上 \(a[i]\)
  2. 删除“紧挨着当前”的 \(a[i-1]\)： 选一段以 \(i-2\) 结尾的不删最优子数组（\(f_0[i-2]\)），把中间的 \(a[i-1]\) 删掉，再接上 \(a[i]\)

点阵图 2：转移依赖（每个箭头都是一次“取 max 的候选来源”）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
列:              i-2              i-1               i
            ┌────────┬────────────────┬────────────────┐
f0（不删）   │   ● A  │      ● B       │      ● C       │
            ├────────┼────────────────┼────────────────┤
f1（至多删） │        │      ● E       │      ● F       │
            └────────┴────────────────┴────────────────┘

依赖箭头（只画与 C、F 有关的）：

B ───────────────▶ C        （f0[i] 依赖 f0[i-1]）
E ───────────────▶ F        （f1[i] 依赖 f1[i-1]）
A ────────(跨一列)────────▶ F        （f1[i] 依赖 f0[i-2]，表示删掉 a[i-1]）

最终：
C = max(B + a[i], a[i])
F = max(E, A) + a[i]

5. 结果为何要比较 f0[i-1]（“删除当前元素”的落点）

由于我们定义的 \(f_1[i]\) 要求 \(a[i]\) 被保留，那么“在最优方案里删掉 \(a[i]\)”这种情况，应该落在哪？

  • 如果删掉当前 \(a[i]\)，那么保留下来的最后一个元素是 \(a[i-1]\)
  • 这正是“以 \(i-1\) 结尾且不删”的最优：\(f_0[i-1]\)

因此代码每轮更新：

1
res = max(res, max(f0[i-1], max(f0[i], f1[i])));

数学上就是维护： \[ \text{res} = \max\Big(\text{res},\ f_0[i],\ f_1[i],\ f_0[i-1]\Big) \] 点阵图 3：答案候选来自哪些格子

1
2
3
4
5
6
7
8
9
10
11
                 i-1                i
            ┌────────────┬────────────────┐
f0（不删）   │   ● f0[i-1] │     ● f0[i]     │
            ├────────────┼────────────────┤
f1（至多删） │            │     ● f1[i]     │
            └────────────┴────────────────┘

答案候选含义：
- f0[i]   ：不删，且以 i 结尾
- f1[i]   ：删一次（或不删），且以 i 结尾并保留 a[i]
- f0[i-1] ：“删掉 a[i]”时，最终保留的结尾在 i-1

6. 与代码逐行对齐的小结

  • f[0][i] 实现 \(f_0[i]\)
  • f[1][i] 实现 \(f_1[i]\)
  • f[1][i] = max(f[0][i-2], f[1][i-1]) + a[i] 精确表达了两类“删法”
  • res 同时比较 f0[i-1] 是为了覆盖“删当前 \(a[i]\)”这一类最优解

7. AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    static const int maxn = 1e5 + 5, neg = 0xcfcfcfcf;
    int maximumSum(vector<int>& arr) {
        int f[2][maxn];
        f[0][0] = 0, f[1][0] = neg;
        f[0][1] = f[1][1] = arr[0];
        int res = arr[0], n = arr.size();
        for (int i = 2; i <= n; ++i) {
            f[0][i] = max(f[0][i - 1] + arr[i - 1], arr[i - 1]);
            f[1][i] = max(f[0][i - 2], f[1][i - 1]) + arr[i - 1];
            res = max(res, max(f[0][i - 1], max(f[0][i], f[1][i])));
        }
        return res;
    }
};

亦可滚动数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    static const int maxn = 1e5 + 5, neg = 0xcfcfcfcf;
    int maximumSum(vector<int>& arr) {
        int a0 = 0, b0 = neg, a1 = arr[0], b1 = arr[0], res = arr[0],
            n = arr.size();
        for (int i = 2; i <= n; ++i) {
            int a2, b2;
            a2 = max(a1 + arr[i - 1], arr[i - 1]);
            b2 = max(a0, b1) + arr[i - 1];
            res = max(res, max(a1, max(a2, b2)));
            a0 = a1, b0 = b1, a1 = a2, b1 = b2;
        }
        return res;
    }
};