3640. 三段式数组 II

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

考点

  • 状态机DP
  • 前后缀分解

思路

设数组为 \[ \text{nums} = [a_0,a_1,\dots,a_{n-1}] \] Trionic 子数组定义为一个连续子数组，可以被划分为三段连续区间：

  1. 第一段：严格递增
  2. 第二段：严格递减
  3. 第三段：严格递增

并且每一段至少包含 两个元素（即每段至少一条比较边）。

目标：求满足上述结构的子数组的 最大元素和。

一、前后缀分解解法

1. 核心思想

前后缀分解的思路是：

枚举中间的严格递减段，并在其左右分别拼接一个最优的严格递增段。

结构示意为： \[ \underbrace{\nearrow\ \nearrow}_{\text{左递增}} \quad \underbrace{\searrow\ \searrow}_{\text{中递减}} \quad \underbrace{\nearrow\ \nearrow}_{\text{右递增}} \] 只要三段都存在，且拼接后形成连续子数组，就可以计算其总和。

2. 状态定义

为此，算法设计了三类辅助数组（均为 1-based 索引）：

(1) 前缀和数组 pre

\[ \text{pre}[i] = \sum_{k=0}^{i-1} a_k \]

用于在 \(O(1)\) 时间内计算任意连续区间的和。

初始化：

1
2
pre[0] = 0;
pre[1] = nums[0];

(2) incTail[i] —— 左递增段

\[ \text{incTail}[i] = \begin{cases} \text{以 } i \text{ 结尾的、严格递增连续子数组的最大和} \\ \text{长度至少为 2} \end{cases} \]

若不存在这样的递增段，则记为负无穷 neg。

转移逻辑（仅当递增成立时）：

  • 新开一个长度为 2 的递增段： \[ a_{i-2} + a_{i-1} \]

  • 或在已有递增段后延长： \[ \text{incTail}[i-1] + a_{i-1} \]

因此： \[ \text{incTail}[i] = \max\left( a_{i-2}+a_{i-1},\ \text{incTail}[i-1]+a_{i-1} \right) \quad \text{若 } a_{i-2} < a_{i-1} \] 否则： \[ \text{incTail}[i] = -\infty \] 初始化：

1
incTail[1] = neg;

(3) incHead[i] —— 右递增段

\[ \text{incHead}[i] = \begin{cases} \text{以 } i \text{ 开头的、严格递增连续子数组的最大和} \\ \text{长度至少为 2} \end{cases} \]

该数组从右向左计算。

转移逻辑（当 \(a_{i-1} < a_i\) 时）：

  • 新开长度 2： \[ a_{i-1}+a_i \]

  • 或向右延长： \[ a_{i-1} + \text{incHead}[i+1] \]

即： \[ \text{incHead}[i] = \max\left( a_{i-1}+a_i,\ \text{incHead}[i+1]+a_{i-1} \right) \] 初始化：

1
incHead[n] = neg;

3. 枚举中间递减段

算法使用双指针 (p,q) 表示一个连续严格递减区间：

  • p：递减段起点（1-based）
  • q：递减段终点（1-based）

维护不变式：

  • 当前区间 [p..q] 是严格递减的
  • 一旦递减性被破坏，重置 p = q

当满足： \[ a_{q-2} > a_{q-1} \] 时，可以尝试将三段拼接。

4. 答案计算公式

三段拼接后的总和为： \[ \begin{aligned} \text{sum} &= \underbrace{\text{incTail}[p]}_{\text{左递增}} + \underbrace{(\text{pre}[q]-\text{pre}[p-1])}_{\text{中递减}} + \underbrace{\text{incHead}[q]}_{\text{右递增}} \\ &\quad - a_{p-1} - a_{q-1} \end{aligned} \] 原因： incTail[p] 和 incHead[q] 都各自包含了端点元素，需要去重。

取所有合法情况中的最大值，即为最终答案。

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
class Solution {
public:
    static const int maxn = 1e5 + 5;
    static const long long neg = LLONG_MIN >> 1;
    long long maxSumTrionic(vector<int>& nums) {
        int n = nums.size();
        long long incHead[maxn], incTail[maxn], pre[maxn];
        pre[0] = 0, pre[1] = nums[0], incTail[1] = neg;
        for (int i = 2; i <= n; ++i) {
            pre[i] = pre[i - 1] + nums[i - 1];
            incTail[i] = neg;
            if (nums[i - 1] > nums[i - 2])
                incTail[i] = max(0LL + nums[i - 1] + nums[i - 2],
                                 incTail[i - 1] + nums[i - 1]);
        }
        incHead[n] = neg;
        for (int i = n - 1; i >= 1; --i) {
            incHead[i] = neg;
            if (nums[i - 1] < nums[i])
                incHead[i] = max(0LL + nums[i - 1] + nums[i],
                                 incHead[i + 1] + nums[i - 1]);
        }
        int p = 1, q = 2;
        long long res = LLONG_MIN >> 1;
        while (q < n) {
            if (nums[q - 1] < nums[q - 2]) {
                res = max(res, pre[q] - pre[p - 1] + incTail[p] - nums[p - 1] +
                                   incHead[q] - nums[q - 1]);
            } else {
                p = q;
            }
            q++;
        }
        return res;
    }
};

二、状态机 DP 解法

1. 核心思想

状态机 DP 的本质是：

在扫描数组时，始终维护“以当前位置为结尾”的、处于不同阶段的最优 Trionic 前缀子数组。

三段结构可以抽象为一个有限状态机： \[ \text{递增}_1 \;\longrightarrow\; \text{递减} \;\longrightarrow\; \text{递增}_2 \] 只需关心当前相邻两个元素的大小关系即可完成状态转移。

2. 状态定义

定义二维 DP 数组（1-based）： \[ f[i][k] = \begin{cases} \text{以 } a_{i-1} \text{ 结尾，处于第 } k \text{ 段的最大和} \end{cases} \] 其中：

  • \(k=0\)：第一段严格递增
  • \(k=1\)：中间严格递减
  • \(k=2\)：第三段严格递增

所有状态均要求对应段 至少已形成一条合法比较边。

3. 初始值

在 \(i=1\)（只有一个元素）时，不可能形成任何合法段： \[ f[1][0] = f[1][1] = f[1][2] = -\infty \] 答案初始化为负无穷： \[ \text{res} = -\infty \]

4. 状态转移方程

设： \[ y = a_{i-2}, \quad x = a_{i-1} \]

(1) 第一段递增（f[i][0]）

仅当 \(y < x\) 时合法： \[ f[i][0] = \max\bigl( y,\ f[i-1][0] \bigr) + x \] 含义：

  • y + x：新开一个长度为 2 的递增段
  • f[i-1][0] + x：延续已有递增段

否则： \[ f[i][0] = -\infty \]

(2) 中间递减段（f[i][1]）

仅当 \(y > x\) 时合法： \[ f[i][1] = \max\bigl( f[i-1][0],\ f[i-1][1] \bigr) + x \] 含义：

  • 从第一段切换到递减段
  • 或继续递减段

否则： \[ f[i][1] = -\infty \]

(3) 第三段递增（f[i][2]）

仅当 \(y < x\) 时合法： \[ f[i][2] = \max\bigl( f[i-1][1],\ f[i-1][2] \bigr) + x \] 含义：

  • 从递减段切换到第三段
  • 或继续第三段

否则： \[ f[i][2] = -\infty \]

5. 答案更新

由于 f[i][2] 表示一个完整合法的 Trionic 子数组，故： \[ \text{res} = \max(\text{res},\ f[i][2]) \]

6. AC代码

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

也可以滚动数组优化常数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    static const int maxn = 1e5 + 5;
    static const long long neg = LLONG_MIN >> 1;
    long long maxSumTrionic(vector<int>& nums) {
        int n = nums.size();
        long long f0 = neg, f1 = neg, f2 = neg, res = neg;
        for (int i = 2; i <= n; ++i) {
            long long y = nums[i - 2], x = nums[i - 1];
            f2 = y < x ? max(f1, f2) + x : neg;
            f1 = x < y ? max(f0, f1) + x : neg;
            f0 = y < x ? max(y, f0) + x : neg;
            res = max(res, f2);
        }
        return res;
    }
};