Kimi LeetCode 3640. 三段式数组 II JavaScript实现
根据搜索到的信息,我来为你提供 LeetCode 3640. Trionic Array II 的 JavaScript 实现。
题目理解
Trionic Array II 是 Trionic Array I 的进阶版本。题目要求:
- 一个 trionic subarray 是一个连续子数组 `nums[l...r]`,满足存在 `l < p < q < r`,使得:
- `nums[l...p]` 严格递增
- `nums[p...q]` 严格递减
- `nums[q...r]` 严格递增
- 要求返回所有 trionic subarray 中 和最大 的那个和
解题思路
参考 Python 解法的思路 :
1. 预处理 DP 数组:
- `dp1[i]`:以 `i` 为起点的严格递增子数组的最大和
- `dp2[i]`:以 `i` 为终点的严格递增子数组的最大和
2. 遍历所有递减段:找到每一段连续严格递减的子数组,计算:
- 递减段的和
- 加上递减段起点前以该点为终点的最大递增和
- 加上递减段终点后以该点为起点的最大递增和
- 注意边界元素去重
JavaScript 实现
```javascript
/**
* @param {number[]} nums
* @return {number}
*/
var maxSumTrionic = function(nums) {
const n = nums.length;
// dp1[i]: 以 i 为起点的严格递增子数组的最大和
// 从右向左计算
const dp1 = new Array(n).fill(-Infinity);
for (let i = n - 2; i >= 0; i--) {
if (nums[i + 1] > nums[i]) {
// 可以选择只取 nums[i] + nums[i+1],或者继续延伸
dp1[i] = Math.max(nums[i] + nums[i + 1], nums[i] + dp1[i + 1]);
}
}
// dp2[i]: 以 i 为终点的严格递增子数组的最大和
// 从左向右计算
const dp2 = new Array(n).fill(-Infinity);
for (let i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
// 可以选择只取 nums[i-1] + nums[i],或者继续延伸
dp2[i] = Math.max(nums[i - 1] + nums[i], nums[i] + dp2[i - 1]);
}
}
let ans = -Infinity;
let i = 1, j = 2;
// 遍历所有可能的递减段 [i, j]
while (j < n - 1) {
// 如果当前不是递减关系,移动指针
if (nums[j] >= nums[i]) {
i = j;
j = j + 1;
continue;
}
// 计算递减段的和
let s = nums[i];
while (j < n - 1 && nums[j] < nums[j - 1]) {
s += nums[j];
j++;
}
j--; // 回退到递减段的最后一个元素
// 计算当前 trionic subarray 的最大和
// s 是递减段的和
// dp2[i] 是以 i 为终点的递增段和(包含 nums[i])
// dp1[j] 是以 j 为起点的递增段和(包含 nums[j])
// 需要减去重复计算的 nums[i] 和 nums[j]
ans = Math.max(ans, s + dp1[j] + dp2[i] - nums[i] - nums[j]);
// 移动到下一个可能的递减段
i = j;
j = j + 1;
}
return ans;
};
```
代码说明
变量 含义
`dp1[i]` 以 `i` 为起点的最长严格递增子数组的最大和
`dp2[i]` 以 `i` 为终点的最长严格递增子数组的最大和
`s` 当前递减段的元素和
`i` 递减段的起点索引
`j` 递减段的终点索引
复杂度分析
- 时间复杂度: O(n) — 预处理两次遍历 + 找递减段一次遍历
- 空间复杂度: O(n) — 两个 DP 数组
示例验证
示例 1: `nums = [0, -2, -1, -3, 0, 2, -1]`
- 输出: `-4`
- 解释: 选择 `l=1, p=2, q=3, r=5`,递减段 `[-1, -3]`,前后配合递增段
示例 2: `nums = [1, 4, 2, 7]`
- 输出: `14`
- 解释: 整个数组就是 trionic,`1+4+2+7 = 14`
> 注意:如果数组中不存在合法的 trionic subarray,根据题意应该返回 `-Infinity` 或题目约定的值。实际提交时可以根据具体测试用例调整边界情况处理。
更多推荐

所有评论(0)