T3640.三段式数组 II

分组循环，prefix sum, dp, https://leetcode.cn/problems/trionic-array-ii/

给你一个长度为 n 的整数数组 nums。

三段式子数组 是一个连续子数组 nums[l...r]（满足 0 <= l < r < n），并且存在下标 l < p < q < r，使得：

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

请你从数组 nums 的所有三段式子数组中找出和最大的那个，并返回其最大和。

示例 1：

输入：nums = [0,-2,-1,-3,0,2,-1]

输出：-4

解释：

选择 l = 1, p = 2, q = 3, r = 5：

nums[l...p] = nums[1...2] = [-2, -1] 严格递增 (-2 < -1)。
nums[p...q] = nums[2...3] = [-1, -3] 严格递减 (-1 > -3)。
nums[q...r] = nums[3...5] = [-3, 0, 2] 严格递增 (-3 < 0 < 2)。
和 = (-2) + (-1) + (-3) + 0 + 2 = -4。

示例 2:

输入: nums = [1,4,2,7]

输出: 14

解释:

选择 l = 0, p = 1, q = 2, r = 3：

nums[l...p] = nums[0...1] = [1, 4] 严格递增 (1 < 4)。
nums[p...q] = nums[1...2] = [4, 2] 严格递减 (4 > 2)。
nums[q...r] = nums[2...3] = [2, 7] 严格递增 (2 < 7)。
和 = 1 + 4 + 2 + 7 = 14。

提示:

4 <= n = nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
保证至少存在一个三段式子数组。

作者：灵茶山艾府链接：https://leetcode.cn/problems/trionic-array-ii/solutions/3741020/fen-zu-xun-huan-on-shi-jian-o1-kong-jian-ewr5/

python

class Solution:
    def maxSumTrionic(self, nums: List[int]) -> int:
        n = len(nums)
        ans = -inf
        i = 0
        while i < n:
            # 第一段
            start = i
            i += 1
            while i < n and nums[i - 1] < nums[i]:
                i += 1
            if i == start + 1:  # 第一段至少要有两个数
                continue

            # 第二段
            peak = i - 1
            res = nums[peak - 1] + nums[peak]  # 第一段的最后两个数必选
            while i < n and nums[i - 1] > nums[i]:
                res += nums[i]  # 第二段的所有元素必选
                i += 1
            if i == peak + 1 or i == n or nums[i - 1] == nums[i]:  # 第二段至少要有两个数，第三段至少要有两个数
                continue

            # 第三段
            bottom = i - 1
            res += nums[i]  # 第三段的前两个数必选（第一个数在上面的循环中加了）
            # 从第三段的第三个数往右，计算最大元素和
            max_s = s = 0
            i += 1
            while i < n and nums[i - 1] < nums[i]:
                s += nums[i]
                max_s = max(max_s, s)
                i += 1
            res += max_s

            # 从第一段的倒数第三个数往左，计算最大元素和
            max_s = s = 0
            for j in range(peak - 2, start - 1, -1):
                s += nums[j]
                max_s = max(max_s, s)
            res += max_s
            ans = max(ans, res)

            i = bottom  # 第三段的起点也是下一个极大三段式子数组的第一段的起点
        return ans

这个问题可以通过 前缀和 结合 动态规划/线性扫描 的思想在 $O (n)$ 时间复杂度内解决。

解题思路

三段式子数组的和可以表示为：

Sum = \sum_{i = l}^{r} n u m s [i] = P [r + 1] - P [l]

其中 $P$ 是前缀和数组（ $P [i]$ 表示前 $i$ 个元素的和）。

为了让和最大，我们需要：

最小化 $P [l]$ ：在满足 $n u m s [l \dots p]$ 严格递增的条件下。
最大化 $P [r + 1]$ ：在满足 $n u m s [q \dots r]$ 严格递增的条件下。
连接中间段：在满足 $n u m s [p \dots q]$ 严格递减的条件下，将前两部分串联。

步骤分解：

计算前缀和：预处理 $P$ 数组。
处理第一段（严格递增 $l \dots p$ ）：定义 $f [p]$ 为以 $p$ 结尾的严格递增序列中，最小的起点前缀和 $P [l]$ 。
- 如果 $n u m s [p] > n u m s [p - 1]$ ，则 $p$ 可以作为递增段的终点。
- 此时 $l$ 可以是 $p - 1$ ，也可以延续之前的最小 $l$ 。
处理第三段（严格递增 $q \dots r$ ）：定义 $g [q]$ 为以 $q$ 开头的严格递增序列中，最大的终点前缀和 $P [r + 1]$ 。
- 如果 $n u m s [q] < n u m s [q + 1]$ ，则 $q$ 可以作为递增段的起点。
- 此时 $r$ 可以是 $q + 1$ ，也可以延续之后的序列。
处理第二段（严格递减 $p \dots q$ ）：定义 $h [q]$ 为以 $q$ 结尾的严格递减序列中，所能衔接的最小 $f [p]$ 。
- 如果 $n u m s [q] < n u m s [q - 1]$ ，则 $q$ 可以作为递减段的终点。
- 此时 $p$ 可以是 $q - 1$ ，也可以延续之前的递减路径。
合并结果：遍历所有的 $q$ ，如果 $h [q]$ 和 $g [q]$ 均存在有效值，则该点可以作为一个“山谷”连接前两个阶段和最后一个阶段，计算 $g [q] - h [q]$ 并取最大值。

Python 代码实现

python

from typing import List

class Solution:
    def maxSumTrionic(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 4:
            return 0
        
        # 1. 计算前缀和 P[i] = nums[0] + ... + nums[i-1]
        P = [0] * (n + 1)
        for i in range(n):
            P[i + 1] = P[i] + nums[i]
            
        INF = float('inf')
        
        # 2. f[p]: 最小的 P[l]，使得 nums[l...p] 严格递增 (l < p)
        f = [INF] * n
        for p in range(1, n):
            if nums[p] > nums[p - 1]:
                # 如果前一个点也能作为递增序列的终点，则取极小值
                if p >= 2 and f[p - 1] != INF:
                    f[p] = min(f[p - 1], P[p - 1])
                else:
                    # 否则只能从 p-1 开始
                    f[p] = P[p - 1]
                    
        # 3. g[q]: 最大的 P[r+1]，使得 nums[q...r] 严格递增 (q < r)
        g = [-INF] * n
        for q in range(n - 2, -1, -1):
            if nums[q] < nums[q + 1]:
                # 如果后一个点也能作为递增序列的起点，则取极大值
                if q + 2 < n + 1 and g[q + 1] != -INF:
                    g[q] = max(g[q + 1], P[q + 2])
                else:
                    # 否则只能到 q+1 结束
                    g[q] = P[q + 2]
                    
        # 4. h[q]: 最小的 f[p]，使得 nums[p...q] 严格递减 (p < q)
        # 这里的 h[q] 实际上帮我们完成了第一段和第二段的组合
        h = [INF] * n
        for q in range(1, n):
            if nums[q] < nums[q - 1]:
                # 如果前一个点也在递减路径中
                # 我们可以从 f[q-1] 开始递减，或者延续之前的最小 f[p]
                prev_val = h[q-1] if q >= 2 else INF
                h[q] = min(prev_val, f[q - 1])
                    
        # 5. 遍历每一个可能的谷点 q，计算最大和
        ans = -INF
        for q in range(n):
            # 必须保证 q 左边有满足条件的递增+递减段，右边有递增段
            if g[q] != -INF and h[q] != INF:
                ans = max(ans, g[q] - h[q])
                
        return int(ans)

复杂度分析

时间复杂度： $O (n)$ 。我们对数组进行了 4 次线性扫描（前缀和、 $f$ 数组、 $g$ 数组、 $h$ 数组），每次扫描的时间复杂度均为 $O (n)$ 。
空间复杂度： $O (n)$ 。需要额外的数组来存储前缀和以及各个状态值。

示例解释 (以示例1为例)

nums = [0, -2, -1, -3, 0, 2, -1]

$n u m s [1. . .2] = [- 2, - 1]$ 递增，此时 $p = 2, f [2] = P [1] = 0$ 。
$n u m s [2. . .3] = [- 1, - 3]$ 递减，此时 $q = 3, h [3] = f [2] = 0$ 。
$n u m s [3. . .5] = [- 3, 0, 2]$ 递增，此时起点为 $q = 3$ ，终点 $r = 5$ ，最大 $P [6] = - 4$ 。
最终结果为 $g [3] - h [3] = - 4 - 0 = - 4$ 。

为了让你更好地理解这道题，我们换一种更直观的方式来拆解它。

1. 核心概念：拆解“三段式”

题目要求的“三段式”子数组其实就像一个 “N”字形 的折线：

第一段（上升）：从某个起点 $l$ 爬到山顶 $p$ 。
第二段（下降）：从山顶 $p$ 下滑到山谷 $q$ 。
第三段（上升）：从山谷 $q$ 爬到终点 $r$ 。

我们的目标是找到这样一段折线，使得它覆盖的所有数字之和最大。

2. 预备知识：前缀和

在数组中，计算一段连续区间的和有一个通用的技巧：前缀和。

假设 P[i] 是前 $i$ 个数字的和。
那么从 $l$ 到 $r$ 的数字之和就是：P[r + 1] - P[l]。

我们要让这个结果最大，其实就是：

让 P[r + 1] 尽可能大。
让 P[l] 尽可能小。

3. 解题思路：找“山谷” $q$

我们要在这个数组里找到所有的“山谷”点 $q$ 。对于每一个可能的 $q$ ，我们要往左看和往右看：

第一步：往右看（处理第三段：上升）

对于每个点 $q$ ，如果它后面跟着一段上升序列，那么这段上升序列能到达的最大前缀和是多少？

我们用一个数组 max_right[q] 记录。
如果从 $q$ 开始不能上升，这个值就是无效。

第二步：往左看（处理第一段和第二段：上升+下降）

我们要找到一个山顶 $p$ ，使得：

从 $l$ 到 $p$ 是上升的（我们要让起点的前缀和 P[l] 最小）。
从 $p$ 到 $q$ 是下降的。

我们用一个数组 min_left[q] 记录在满足这种“先升后降”到 $q$ 的路径中，最小的起点前缀和 P[l] 是多少。

第三步：计算答案

遍历每一个点 $q$ ，如果它既能通过“先升后降”来到达（有 min_left[q]），又能通过“上升”去往后面（有 max_right[q]），那么这个点 $q$ 就可以作为一个合格的山谷。

当前山谷能获得的最大和 = max_right[q] - min_left[q]。
我们在所有可能的 $q$ 中选一个最大的结果即可。

4. 形象化的例子

假设 nums = [1, 4, 2, 7]：

第一段 (1→4)： $l = 0, p = 1$ 。起点前缀和 P[0] = 0。
第二段 (4→2)： $p = 1, q = 2$ 。山谷是 $q = 2$ ，对应的最小起点前缀和还是 P[0] = 0。
第三段 (2→7)： $q = 2, r = 3$ 。终点后的前缀和 P[4] = 1+4+2+7 = 14。
结果：P[4] - P[0] = 14 - 0 = 14。

5. 代码实现（更简洁的注释）

python

from typing import List

class Solution:
    def maxSumTrionic(self, nums: List[int]) -> int:
        n = len(nums)
        # 1. 计算前缀和 P
        P = [0] * (n + 1)
        for i in range(n):
            P[i + 1] = P[i] + nums[i]
            
        INF = float('inf')
        
        # 2. f[i]: 满足 [l...i] 严格递增时，最小的起点前缀和 P[l]
        f = [INF] * n
        for i in range(1, n):
            if nums[i] > nums[i-1]:
                # 如果前一个点也是递增过来的，可以延续之前的最小值，或者从 i-1 开始
                f[i] = min(f[i-1], P[i-1]) if f[i-1] != INF else P[i-1]

        # 3. h[i]: 满足 [l...p] 升, [p...i] 降时，最小的起点前缀和 P[l]
        # 这步是把第一段和第二段结合起来
        h = [INF] * n
        for i in range(1, n):
            if nums[i] < nums[i-1]:
                # 如果 i-1 是山顶，可以从 f[i-1] 转移；如果 i-1 也在下降，延续 h[i-1]
                h[i] = min(h[i-1], f[i-1])

        # 4. g[i]: 满足 [i...r] 严格递增时，最大的终点前缀和 P[r+1]
        g = [-INF] * n
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i+1]:
                # 如果后一个点也是递增的，延续最大值，或者到 i+1 结束
                g[i] = max(g[i+1], P[i+2]) if g[i+1] != -INF else P[i+2]
                
        # 5. 遍历每个山谷点 i，计算最大差值
        ans = -INF
        for i in range(n):
            if h[i] != INF and g[i] != -INF:
                ans = max(ans, g[i] - h[i])
                
        return int(ans)

为什么这个方法快？

因为它只把数组从左到右、从右到左扫了几遍（时间复杂度 $O (n)$ ），没有嵌套循环。这就像是在地图上提前标好了所有的上坡路和下坡路，最后只需要看一眼在哪里转弯最划算。

T3640.三段式数组 II ​

T3640.三段式数组 II