3640. Trionic Array II

📘 題目敘述

給你一個長度為 n 的整數陣列 nums。

一個 trionic subarray 是一個連續子陣列 nums[l...r]（滿足 0 <= l < r < n），並且存在索引 l < p < q < r 使得：

nums[l...p] 是嚴格遞增
nums[p...q] 是嚴格遞減
nums[q...r] 是嚴格遞增

請回傳 nums 中任意 trionic subarray 的最大總和。

條件限制

4 <= n = nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
保證至少存在一個 trionic subarray。

🧠 解題思路

trionic 的型態一定是：

上升（一段） → 下降（一段） → 上升（一段），而且三段都必須「至少包含一個相鄰關係」（也就是每段都要真的發生嚴格上升/下降）。

我這份 code 用 一次掃描 + 三個 DP 狀態，每次只看相鄰的 (nums[i-1], nums[i])，把「以 nums[i] 當結尾」的最佳 trionic 前綴總和更新出來。

三個狀態在代表什麼（都以「目前走到的最後一個元素 = y」為結尾）

令 y = nums[i]，x = nums[i-1]。

up1：目前正在「第一段嚴格遞增」的最佳總和（至少要有一個上升步驟）
- 也就是形狀像 ... < x < y，最後一步是上升
down：目前正在「第二段嚴格遞減」的最佳總和（前面必須已經完成第一段上升）
- 也就是形狀像 上升完後 ... > y，最後一步是下降
up2：目前正在「第三段嚴格遞增」的最佳總和（前面必須已經經過上升+下降）
- 也就是已經形成 trionic，最後一步再上升，up2 一旦成立就可以拿來更新答案

另外：

一旦遇到 x == y，嚴格遞增/遞減都不可能延續，所以三個狀態全部清空。

為什麼更新式長這樣

每一步只分三種情況：

1) `x < y`（上升）

第一段上升可以延續，或從這個上升步驟重新開一段：
- up1 = max(up1, x) + y
  - up1：延續舊的上升段（把 y 接上去）
  - x：代表「從 x→y 這一步」新開一個上升段，總和就是 x + y
第三段上升也可以延續，或從「下降段」轉進第三段：
- up2 = max(up2, down) + y
  - up2：延續舊的第三段上升
  - down：把「下降段」接上這一步上升，正式進入第三段
只要 up2 有值，就代表已形成 trionic subarray，可以更新答案：
- ans = max(ans, up2)
注意：上升時不能同時處在下降段，所以：
- down = NEG

2) `x > y`（下降）

下降段可以延續，或從第一段上升轉進下降：
- down = max(down, up1) + y
  - down：延續舊的下降段
  - up1：從第一段轉入下降段（開始第二段）
一旦開始下降，就不能還保留「正在上升」的狀態（段落順序會亂掉），所以：
- up1 = NEG
- up2 = NEG

3) `x == y`（相等）

嚴格遞增/遞減都不成立，直接清空：
- up1 = down = up2 = NEG

所有變數

nums：輸入陣列
NEG：極小值（代表「這個狀態目前不可能成立」）
up1：第一段嚴格遞增的最佳總和（以目前元素結尾）
down：第二段嚴格遞減的最佳總和（以目前元素結尾）
up2：第三段嚴格遞增的最佳總和（以目前元素結尾）
ans：目前找到的最大 trionic subarray 總和
x：nums[i-1]（上一個元素）
y：nums[i]（目前元素）

🪜 主要流程步驟

1. 初始化 DP 狀態

全部設成不可能：NEG
ans 也先設成 NEG

2. 由左到右掃描相鄰的 `(x, y)`

對每個 i = 1 ... n-1：

若 x < y：
- 更新 up1
- 更新 up2
- 用 up2 更新 ans
- 清空 down
若 x > y：
- 更新 down
- 清空 up1、up2
若 x == y：
- 清空 up1、down、up2

3. 回傳答案

return ans

💻 程式碼實作

class Solution {
public:
    long long maxSumTrionic(vector<int>& nums) {
        const long long NEG = LLONG_MIN / 2;
        long long up1 = NEG, down = NEG, up2 = NEG;
        long long ans = NEG;
        int n = nums.size();
        for (int i = 1; i < n; i++) {
            long long x = nums[i - 1], y = nums[i];
            if (x < y) { // 上升
                up1 = max(up1, x) + y;
                up2 = max(up2, down) + y;
                ans = max(ans, up2);
                down = NEG;
            } else if (nums[i - 1] > nums[i]) { // 下降
                down = max(down, up1) + y;
                up1 = NEG;
                up2 = NEG;
            } else { // 相等
                up1 = down = up2 = NEG;
            }
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/trionic-array-ii/