周赛250803

Q4. 三段式数组 II

1. 题目大意

给定一个整数数组 nums，请你在所有三段式子数组中找出最大和。

三段式子数组定义为一个连续子数组 nums[l...r]，满足其中存在下标 l < p < q < r，使得这三个片段满足：

  • nums[l...p] 严格递增
  • nums[p...q] 严格递减
  • nums[q...r] 严格递增

请你找出这样的所有子数组中和最大的一个，并返回其和。

2. 实现思路

这是一道状态转移型动态规划题。目标是枚举所有可能的三段式子数组，但暴力会超时（O(n⁴)）。因此使用线性动态规划来表示每一个阶段的转移过程。

我们设计三个数组分别表示：

  • inc[i]：表示以 i 结尾的「严格递增」子数组的最大和（第一段）
  • des[i]：表示以 i 结尾的「严格递减」子数组的最大和（第二段）
  • tri[i]：表示以 i 结尾的完整三段式子数组（递增 + 递减 + 递增）的最大和（最终目标）

状态转移逻辑如下：

  • 如果当前 nums[i] > nums[i-1]：
    • 可以更新 inc[i] = max(inc[i-1] + nums[i], nums[i-1] + nums[i]) （从 inc[i-1] 转移，或新开始）
    • 可以从 des[i-1] 直接转入第三段，更新 tri[i] = des[i-1] + nums[i]
    • 可以继续接在 tri[i-1] 上更新 tri[i] = tri[i-1] + nums[i]
  • 如果当前 nums[i] < nums[i-1]：
    • 可以从 inc[i-1] 开始进入下降段，更新 des[i] = inc[i-1] + nums[i]
    • 可以继续接在 des[i-1] 后面，更新 des[i] = des[i-1] + nums[i]

3. 代码实现

from math import inf
from typing import List

class Solution:
    def maxSumTrionic(self, nums: List[int]) -> int:
        n = len(nums)
        M = -inf  # 初始化为负无穷

        # inc[i]：以 i 结尾的严格递增段最大和
        # des[i]：以 i 结尾的严格递减段最大和
        # tri[i]：以 i 结尾的三段式数组最大和
        inc = [M] * n 
        des = [M] * n 
        tri = [M] * n 

        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                # 第一段：递增
                inc[i] = nums[i - 1] + nums[i]
                if inc[i - 1] != M:
                    inc[i] = max(inc[i], inc[i - 1] + nums[i])
                # 第三段开始：从 des 转过来
                if des[i - 1] != M:
                    tri[i] = max(tri[i], des[i - 1] + nums[i])
                # 第三段继续：从 tri[i-1] 转移
                if tri[i - 1] != M:
                    tri[i] = max(tri[i], tri[i - 1] + nums[i])

            if nums[i] < nums[i - 1]:
                # 第二段：递减
                if des[i - 1] != M:
                    des[i] = max(des[i], des[i - 1] + nums[i])
                if inc[i - 1] != M:
                    des[i] = max(des[i], inc[i - 1] + nums[i])

        return max(tri)