2026-01-11：三段式数组Ⅱ。用go语言，给定长度为 n 的整数序列 nums，要求选出一个包含至少四个元素的连续区间 [a, b]（0 ≤ a < b < n

福大大架构师每日一题

发布于 2026-01-12 11:01:11

1190

2026-01-11：三段式数组Ⅱ。用go语言，给定长度为 n 的整数序列 nums，要求选出一个包含至少四个元素的连续区间 [a, b]（0 ≤ a < b < n），并在区间内选两个切分点 a < i < j < b，使得区间被分成三段：第一段从 a 到 i 元素严格上升，第二段从 i 到 j 元素严格下降，第三段从 j 到 b 元素又严格上升。在所有满足此模式的连续区间中，找出其元素和的最大值并返回该最大和。

4 <= n = nums.length <= 100000。

-1000000000 <= nums[i] <= 1000000000。

保证至少存在一个三段式子数组。

输入: 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。

题目来自力扣3640。

🔍 算法步骤详解

1. 初始化阶段 算法定义了四个关键变量，并赋予它们一个极小的初始值（negInf，约为最小整数的一半，以防止后续加法运算时溢出）：
- • ans：用于记录遍历过程中找到的满足条件的最大子数组和。
- • f1：动态规划状态变量，追踪当前可能处于**第一段（严格递增）**的序列的最大和。
- • f2：动态规划状态变量，追踪当前可能处于**第二段（严格递减）**的序列的最大和。
- • f3：动态规划状态变量，追踪当前可能处于**第三段（严格递增）**的序列的最大和。
2. 遍历与状态转移 算法从数组的第二个元素开始遍历（i 从 1 到 len(nums)-1）。在每一步，它比较当前元素 y（即 nums[i]）和前一个元素 x（即 nums[i-1]），并根据大小关系更新三个状态变量：
- • 情况一：x < y（上升趋势） 这种情况可能意味着延续第一段的上升，或者开启第三段的上升。
  - • 更新 f3（第三段）：f3 可以从上一状态 f3（延续第三段）或 f2（第二段结束，开始第三段）转移过来，并加上当前元素 y。然后，用这个新的 f3 值尝试更新全局最大和 ans。
  - • 更新 f1（第一段）：f1 可以从其上一状态延续并加上 y，这表示第一段在延长。
  - • 重置 f2：由于出现了上升趋势，任何正在构建的第二段（下降段）必须中断，因此将 f2 重置为 negInf。
- • 情况二：x > y（下降趋势） 这种情况可能意味着从第一段过渡到第二段，或者延续第二段的下降。
  - • 更新 f2（第二段）：f2 可以从其上一状态延续，或者从 f1（第一段结束，开始第二段）转移过来，并加上当前元素 y。
  - • 重置 f1 和 f3：一旦进入下降趋势，之前可能的第一段和第三段状态变得无效，因此将 f1 和 f3 重置为 negInf。
- • 情况三：x == y（相等元素） 根据题目要求，每一段都必须是“严格”单调的。因此，只要出现相邻元素相等，当前正在构建的任何三段式模式都会立即失效。
  - • 完全重置状态：将 f1, f2, f3 全部重置为 negInf，表示需要重新开始寻找有效的序列模式。
3. 结果返回 在遍历完整个数组后，变量 ans 中存储的就是所有满足条件的三段式连续子数组的最大和，算法将其转换为 int64 类型后返回。

⏱️ 复杂度分析

• 时间复杂度：O(n) 算法仅对输入数组 nums 进行了一次线性遍历，循环内的所有操作（比较、加法、取最大值）都是常数时间 O(1)。因此，总的时间复杂度与数组长度 n 成线性关系，为 O(n)。
• 额外空间复杂度：O(1) 算法在执行过程中，仅使用了固定数量的额外变量（ans, f1, f2, f3, i, x, y）。这些变量的数量不随输入数组的大小 n 而变化。因此，额外的空间复杂度是常数阶 O(1)。

Go完整代码如下：

package main

import (
    "fmt"
    "math"
)

func maxSumTrionic(nums []int)int64 {
    const negInf = math.MinInt / 2// 除 2 防止下面加法（和负数相加）溢出
    ans, f1, f2, f3 := negInf, negInf, negInf, negInf
    for i := 1; i < len(nums); i++ {
        x, y := nums[i-1], nums[i]
        if x < y { // 第一段或者第三段
            f3 = max(f3, f2) + y
            ans = max(ans, f3)
            f2 = negInf
            f1 = max(f1, x) + y
        } elseif x > y { // 第二段
            f2 = max(f2, f1) + y
            f1, f3 = negInf, negInf
        } else {
            f1, f2, f3 = negInf, negInf, negInf
        }
    }
    returnint64(ans)
}

func main() {
    nums := []int{1, 4, 2, 7}
    result := maxSumTrionic(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def maxSumTrionic(nums):
    NEG_INF = -10**18  # 使用一个足够小的负数，避免溢出
    ans = f1 = f2 = f3 = NEG_INF
    
    for i in range(1, len(nums)):
        x, y = nums[i-1], nums[i]
        if x < y:  # 第一段或者第三段
            f3 = max(f3, f2) + y
            ans = max(ans, f3)
            f2 = NEG_INF
            f1 = max(f1, x) + y
        elif x > y:  # 第二段
            f2 = max(f2, f1) + y
            f1 = f3 = NEG_INF
        else:
            f1 = f2 = f3 = NEG_INF
    
    return ans

if __name__ == "__main__":
    nums = [1, 4, 2, 7]
    result = maxSumTrionic(nums)
    print(result)

C++完整代码如下：

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

long long maxSumTrionic(vector<int>& nums) {
    const long long NEG_INF = LLONG_MIN / 2; // 除 2 防止加法溢出
    long long ans = NEG_INF, f1 = NEG_INF, f2 = NEG_INF, f3 = NEG_INF;

    for (size_t i = 1; i < nums.size(); i++) {
        int x = nums[i-1], y = nums[i];
        if (x < y) { // 第一段或者第三段
            f3 = max(f3, f2) + y;
            ans = max(ans, f3);
            f2 = NEG_INF;
            f1 = max(f1, (long long)x) + y;
        } elseif (x > y) { // 第二段
            f2 = max(f2, f1) + y;
            f1 = f3 = NEG_INF;
        } else {
            f1 = f2 = f3 = NEG_INF;
        }
    }

    return ans;
}

int main() {
    vector<int> nums = {1, 4, 2, 7};
    long long result = maxSumTrionic(nums);
    cout << result << endl;

    return0;
}