3640. 三调子数组 II

Hard

题目描述

给你一个长度为 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
保证至少存在一个三调子数组

解题思路

这个问题需要找到一个连续子数组，它有三个阶段：递增→递减→递增。我们可以使用动态规划来解决。

核心思路是定义四个状态数组：

dp0[i]：以位置 i 结尾，还在准备阶段（可以开始递增）的最大和
dp1[i]：以位置 i 结尾，正在第一个递增阶段的最大和
dp2[i]：以位置 i 结尾，正在递减阶段的最大和
dp3[i]：以位置 i 结尾，正在第二个递增阶段的最大和

状态转移的关键在于：

当 nums[i] > nums[i-1] 时，可以：
- 继续或开始递增阶段：dp1[i] = max(dp1[i-1] + nums[i], dp0[i-1] + nums[i])
- 继续或开始第二个递增阶段：dp3[i] = max(dp3[i-1] + nums[i], dp2[i-1] + nums[i])
- 延续准备阶段：dp0[i] = dp0[i-1] + nums[i]
当 nums[i] < nums[i-1] 时，可以：
- 继续或开始递减阶段：dp2[i] = max(dp2[i-1] + nums[i], dp1[i-1] + nums[i])

最终答案是 dp3 数组中的最大值，因为只有完成所有三个阶段才是有效的三调子数组。

代码实现

class Solution {
public:
    long long maxSumTrionic(vector<int>& nums) {
        int n = nums.size();
        vector<long long> dp0(n), dp1(n), dp2(n), dp3(n);
        
        // 初始化
        dp0[0] = nums[0];
        dp1[0] = dp2[0] = dp3[0] = LLONG_MIN;
        
        for (int i = 1; i < n; i++) {
            // 默认设为最小值
            dp0[i] = dp1[i] = dp2[i] = dp3[i] = LLONG_MIN;
            
            if (nums[i] > nums[i-1]) {
                // 可以开始或继续递增
                if (dp0[i-1] != LLONG_MIN) {
                    dp0[i] = dp0[i-1] + nums[i];
                    dp1[i] = max(dp1[i], dp0[i-1] + nums[i]);
                }
                if (dp1[i-1] != LLONG_MIN) {
                    dp1[i] = max(dp1[i], dp1[i-1] + nums[i]);
                }
                // 可以开始或继续第二个递增阶段
                if (dp2[i-1] != LLONG_MIN) {
                    dp3[i] = max(dp3[i], dp2[i-1] + nums[i]);
                }
                if (dp3[i-1] != LLONG_MIN) {
                    dp3[i] = max(dp3[i], dp3[i-1] + nums[i]);
                }
            } else if (nums[i] < nums[i-1]) {
                // 可以开始或继续递减
                if (dp1[i-1] != LLONG_MIN) {
                    dp2[i] = max(dp2[i], dp1[i-1] + nums[i]);
                }
                if (dp2[i-1] != LLONG_MIN) {
                    dp2[i] = max(dp2[i], dp2[i-1] + nums[i]);
                }
            }
        }
        
        long long result = LLONG_MIN;
        for (int i = 0; i < n; i++) {
            if (dp3[i] != LLONG_MIN) {
                result = max(result, dp3[i]);
            }
        }
        return result;
    }
};

class Solution:
    def maxSumTrionic(self, nums: List[int]) -> int:
        n = len(nums)
        dp0 = [float('-inf')] * n
        dp1 = [float('-inf')] * n
        dp2 = [float('-inf')] * n
        dp3 = [float('-inf')] * n
        
        # 初始化
        dp0[0] = nums[0]
        
        for i in range(1, n):
            if nums[i] > nums[i-1]:
                # 可以开始或继续递增
                if dp0[i-1] != float('-inf'):
                    dp0[i] = dp0[i-1] + nums[i]
                    dp1[i] = max(dp1[i], dp0[i-1] + nums[i])
                if dp1[i-1] != float('-inf'):
                    dp1[i] = max(dp1[i], dp1[i-1] + nums[i])
                # 可以开始或继续第二个递增阶段
                if dp2[i-1] != float('-inf'):
                    dp3[i] = max(dp3[i], dp2[i-1] + nums[i])
                if dp3[i-1] != float('-inf'):
                    dp3[i] = max(dp3[i], dp3[i-1] + nums[i])
            elif nums[i] < nums[i-1]:
                # 可以开始或继续递减
                if dp1[i-1] != float('-inf'):
                    dp2[i] = max(dp2[i], dp1[i-1] + nums[i])
                if dp2[i-1] != float('-inf'):
                    dp2[i] = max(dp2[i], dp2[i-1] + nums[i])
        
        return max(val for val in dp3 if val != float('-inf'))

public class Solution {
    public long MaxSumTrionic(int[] nums) {
        int n = nums.Length;
        long[] dp0 = new long[n], dp1 = new long[n], dp2 = new long[n], dp3 = new long[n];
        
        // 初始化
        for (int i = 0; i < n; i++) {
            dp0[i] = dp1[i] = dp2[i] = dp3[i] = long.MinValue;
        }
        dp0[0] = nums[0];
        
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i-1]) {
                // 可以开始或继续递增
                if (dp0[i-1] != long.MinValue) {
                    dp0[i] = dp0[i-1] + nums[i];
                    dp1[i] = Math.Max(dp1[i], dp0[i-1] + nums[i]);
                }
                if (dp1[i-1] != long.MinValue) {
                    dp1[i] = Math.Max(dp1[i], dp1[i-1] + nums[i]);
                }
                // 可以开始或继续第二个递增阶段
                if (dp2[i-1] != long.MinValue) {
                    dp3[i] = Math.Max(dp3[i], dp2[i-1] + nums[i]);
                }
                if (dp3[i-1] != long.MinValue) {
                    dp3[i] = Math.Max(dp3[i], dp3[i-1] + nums[i]);
                }
            } else if (nums[i] < nums[i-1]) {
                // 可以开始或继续递减
                if (dp1[i-1] != long.MinValue) {
                    dp2[i] = Math.Max(dp2[i], dp1[i-1] + nums[i]);
                }
                if (dp2[i-1] != long.MinValue) {
                    dp2[i] = Math.Max(dp2[i], dp2[i-1] + nums[i]);
                }
            }
        }
        
        long result = long.MinValue;
        for (int i = 0; i < n; i++) {
            if (dp3[i] != long.MinValue) {
                result = Math.Max(result, dp3[i]);
            }
        }
        return result;
    }
}

var maxSumTrionic = function(nums) {
    const n = nums.length;
    const dp0 = new Array(n).fill(-Infinity);
    const dp1 = new Array(n).fill(-Infinity);
    const dp2 = new Array(n).fill(-Infinity);
    const dp3 = new Array(n).fill(-Infinity);
    
    // 初始化
    dp0[0] = nums[0];
    
    for (let i = 1; i < n; i++) {
        if (nums[i] > nums[i-1]) {
            // 可以开始或继续递增
            if (dp0[i-1] !== -Infinity) {
                dp0[i] = dp0[i-1] + nums[i];
                dp1[i] = Math.max(dp1[i], dp0[i-1] + nums[i]);
            }
            if (dp1[i-1] !== -Infinity) {
                dp1[i] = Math.max(dp1[i], dp1[i-1] + nums[i]);
            }
            // 可以开始或继续第二个递增阶段
            if (dp2[i-1] !== -Infinity) {
                dp3[i] = Math.max(dp3[i], dp2[i-1] + nums[i]);
            }
            if (dp3[i-1] !== -Infinity) {
                dp3[i] = Math.max(dp3[i], dp3[i-1] + nums[i]);
            }
        } else if (nums[i] < nums[i-1]) {
            // 可以开始或继续递减
            if (dp1[i-1] !== -Infinity) {
                dp2[i] = Math.max(dp2[i], dp1[i-1] + nums[i]);
            }
            if (dp2[i-1] !== -Infinity) {
                dp2[i] = Math.max(dp2[i], dp2[i-1] + nums[i]);
            }
        }
    }
    
    return Math.max(...dp3.filter(val => val !== -Infinity));
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(n)，遍历数组一次，每个位置的状态转移都是常数时间
空间复杂度	O(n)，需要四个长度为 n 的数组存储动态规划状态

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析