3640. 三段式数组 II

September 12, 2026 · View on GitHub

English Version

题目描述

给你一个长度为 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⁵
-10⁹ <= nums[i] <= 10⁹
保证至少存在一个三段式子数组。

解法

方法一：分组循环

思考

求权和最大的三段式子数组。枚举所有峰谷为平方级。相邻三段式会共享上升段，可用分组循环在线性时间内枚举极大三段。

指针依次切出升、降、升三段；中段或末段退化则跳过。极大段的和由中部固定部分、左升段向左的最大后缀、右升段向右的最大前缀组成。

第三段上升可作为下一段的第一段，故将指针回退到谷底 $q$ 。全程每个下标进出常数次。

我们可以遍历数组，寻找所有可能的极大三段式子数组，从而计算其和并更新最大值。

我们定义一个指针 $i$ ，初始时 $i = 0$ ，表示当前指向数组的第一个元素。我们将 $i$ 向右移动，直到找到第一个不满足严格递增的元素，即 $nums[i-1] \geq nums[i]$ 。如果此时 $i = l + 1$ ，说明这一段只有一个元素，无法形成递增序列，因此继续下一个循环。

接下来，我们定义指针 $p$ ，表示当前递增段的结束位置。然后找出第二段严格递减的部分，如果这一段只有一个元素或者到达数组末尾，或者出现相等的元素，则继续下一个循环。

然后我们定义指针 $q$ ，表示当前递减段的结束位置。接着找出第三段严格递增的部分，这时，我们就找到了一个极大的三段式子数组。那么这个三段式子数组的最大和，由以下几个部分组成：

下标范围 $[p-2,..,q+1]$ 的元素之和
从 $p-3$ 向左扩展的最大递增子数组之和，如果不存在则为 0
从 $q+2$ 向右扩展的最大递增子数组之和，如果不存在则为 0。

我们计算出这个三段式子数组的和后，更新答案。然后将指针 $i$ 移动到 $q$ 位置，这是因为第三段的递增部分可以作为下一次循环的第一段递增部分。

遍历结束后，返回答案即可。

时间复杂度 $O(n)$ ，其中 $n$ 是数组的长度。空间复杂度 $O(1)$ ，只使用了常数级别的额外空间。

Python3

class Solution:
    def maxSumTrionic(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0
        ans = -inf
        while i < n:
            l = i
            i += 1
            while i < n and nums[i - 1] < nums[i]:
                i += 1
            if i == l + 1:
                continue

            p = i - 1
            s = nums[p - 1] + nums[p]
            while i < n and nums[i - 1] > nums[i]:
                s += nums[i]
                i += 1
            if i == p + 1 or i == n or nums[i - 1] == nums[i]:
                continue

            q = i - 1
            s += nums[i]
            i += 1
            mx = t = 0
            while i < n and nums[i - 1] < nums[i]:
                t += nums[i]
                i += 1
                mx = max(mx, t)
            s += mx

            mx = t = 0
            for j in range(p - 2, l - 1, -1):
                t += nums[j]
                mx = max(mx, t)
            s += mx

            ans = max(ans, s)
            i = q
        return ans

Java

class Solution {
    public long maxSumTrionic(int[] nums) {
        int n = nums.length;
        int i = 0;
        long ans = Long.MIN_VALUE;
        while (i < n) {
            int l = i;
            i += 1;
            while (i < n && nums[i - 1] < nums[i]) {
                i += 1;
            }
            if (i == l + 1) {
                continue;
            }

            int p = i - 1;
            long s = nums[p - 1] + nums[p];
            while (i < n && nums[i - 1] > nums[i]) {
                s += nums[i];
                i += 1;
            }
            if (i == p + 1 || i == n || nums[i - 1] == nums[i]) {
                continue;
            }

            int q = i - 1;
            s += nums[i];
            i += 1;
            long mx = 0, t = 0;
            while (i < n && nums[i - 1] < nums[i]) {
                t += nums[i];
                i += 1;
                mx = Math.max(mx, t);
            }
            s += mx;

            mx = 0;
            t = 0;
            for (int j = p - 2; j >= l; j--) {
                t += nums[j];
                mx = Math.max(mx, t);
            }
            s += mx;

            ans = Math.max(ans, s);
            i = q;
        }
        return ans;
    }
}

C++

class Solution {
public:
    long long maxSumTrionic(vector<int>& nums) {
        int n = nums.size();
        int i = 0;
        long long ans = LLONG_MIN;
        while (i < n) {
            int l = i;
            i += 1;
            while (i < n && nums[i - 1] < nums[i]) {
                i += 1;
            }
            if (i == l + 1) {
                continue;
            }

            int p = i - 1;
            long long s = nums[p - 1] + nums[p];
            while (i < n && nums[i - 1] > nums[i]) {
                s += nums[i];
                i += 1;
            }
            if (i == p + 1 || i == n || nums[i - 1] == nums[i]) {
                continue;
            }

            int q = i - 1;
            s += nums[i];
            i += 1;
            long long mx = 0, t = 0;
            while (i < n && nums[i - 1] < nums[i]) {
                t += nums[i];
                i += 1;
                mx = max(mx, t);
            }
            s += mx;

            mx = 0, t = 0;
            for (int j = p - 2; j >= l; j--) {
                t += nums[j];
                mx = max(mx, t);
            }
            s += mx;

            ans = max(ans, s);
            i = q;
        }
        return ans;
    }
};

Go

func maxSumTrionic(nums []int) int64 {
	n := len(nums)
	i := 0
	ans := int64(math.MinInt64)
	for i < n {
		l := i
		for i++; i < n && nums[i-1] < nums[i]; {
			i++
		}
		if i == l+1 {
			continue
		}

		p := i - 1
		s := int64(nums[p-1]) + int64(nums[p])
		for i < n && nums[i-1] > nums[i] {
			s += int64(nums[i])
			i++
		}
		if i == p+1 || i == n || nums[i-1] == nums[i] {
			continue
		}

		q := i - 1
		s += int64(nums[i])
		i++
		var mx, t int64
		for i < n && nums[i-1] < nums[i] {
			t += int64(nums[i])
			i++
			mx = max(mx, t)
		}
		s += mx

		mx, t = 0, 0
		for j := p - 2; j >= l; j-- {
			t += int64(nums[j])
			mx = max(mx, t)
		}
		s += mx

		ans = max(ans, s)
		i = q
	}
	return ans
}

TypeScript

function maxSumTrionic(nums: number[]): number {
    const n = nums.length;
    let i = 0;
    let ans = -Infinity;

    while (i < n) {
        const l = i;
        i += 1;

        while (i < n && nums[i - 1] < nums[i]) i += 1;
        if (i === l + 1) continue;

        const p = i - 1;
        let s = nums[p - 1] + nums[p];

        while (i < n && nums[i - 1] > nums[i]) {
            s += nums[i];
            i += 1;
        }
        if (i === p + 1 || i === n || nums[i - 1] === nums[i]) continue;

        const q = i - 1;
        s += nums[i];
        i += 1;

        let mx = 0,
            t = 0;
        while (i < n && nums[i - 1] < nums[i]) {
            t += nums[i];
            i += 1;
            mx = Math.max(mx, t);
        }
        s += mx;

        mx = 0;
        t = 0;
        for (let j = p - 2; j >= l; j--) {
            t += nums[j];
            mx = Math.max(mx, t);
        }
        s += mx;

        ans = Math.max(ans, s);
        i = q;
    }

    return ans;
}

Rust

impl Solution {
    pub fn max_sum_trionic(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut i = 0;
        let mut ans = i64::MIN;
        while i < n {
            let l = i;
            i += 1;
            while i < n && nums[i - 1] < nums[i] {
                i += 1;
            }
            if i == l + 1 {
                continue;
            }

            let p = i - 1;
            let mut s = nums[p - 1] as i64 + nums[p] as i64;
            while i < n && nums[i - 1] > nums[i] {
                s += nums[i] as i64;
                i += 1;
            }
            if i == p + 1 || i == n || nums[i - 1] == nums[i] {
                continue;
            }

            let q = i - 1;
            s += nums[i] as i64;
            i += 1;
            let mut mx = 0i64;
            let mut t = 0i64;
            while i < n && nums[i - 1] < nums[i] {
                t += nums[i] as i64;
                i += 1;
                mx = mx.max(t);
            }
            s += mx;

            mx = 0;
            t = 0;
            let mut j = p as isize - 2;
            while j >= l as isize {
                t += nums[j as usize] as i64;
                mx = mx.max(t);
                j -= 1;
            }
            s += mx;

            ans = ans.max(s);
            i = q;
        }
        ans
    }
}