Kimi k2.6 LeetCode 3041. 修改数组后最大化数组中的连续元素数目 JavaScript实现

这道题的核心思路是 排序 动态规划。思路分析1. 排序先将数组排序方便处理连续关系。2. 动态规划设 dp[v] 表示以值 v 结尾的最长连续序列长度。对于每个元素 x- 不变值为 x需要前面有以 x-1 结尾的序列 → dp[x] dp[x-1] 1- 1值为 x1需要前面有以 x 结尾的序列 → dp[x1] dp[x] 13. 处理顺序排序后按顺序处理对于重复元素后处理的可以基于前面已更新的状态。JavaScript 实现javascript/*** param {number[]} nums* return {number}*/var maxSelectedElements function(nums) {// 排序nums.sort((a, b) a - b);// dp[v] 表示以值 v 结尾的最长连续序列长度// 使用 Map 存储因为值域较大但有效状态有限const dp new Map();let res 0;for (const x of nums) {// 选项1x 不变以 x 结尾const len1 (dp.get(x - 1) || 0) 1;// 选项2x 1以 x1 结尾// 注意这里 dp.get(x) 可能已经被当前轮次前面相同元素更新过const len2 (dp.get(x) || 0) 1;// 更新 dp[x]不变的情况dp.set(x, Math.max(dp.get(x) || 0, len1));// 更新 dp[x1]1 的情况dp.set(x 1, Math.max(dp.get(x 1) || 0, len2));// 更新答案res Math.max(res, dp.get(x), dp.get(x 1));}return res;};验证示例示例 1nums [2,1,5,1,1]- 排序后[1,1,1,2,5]- 处理 1dp[1]1, dp[2]1, res1- 处理第二个 1dp[1]1, dp[2]max(1, 11)2, res2- 处理第三个 1dp[1]1, dp[2]max(2, 11)2, res2- 处理 2dp[2]max(2, dp[1]12)2, dp[3]dp[2]13, res3- 处理 5dp[5]1, dp[6]1, res3- 结果3 ✓示例 2nums [1,4,7,10]- 排序后[1,4,7,10]- 各元素互不相邻每个只能单独成序列- 结果1 ✓复杂度分析- 时间复杂度O(n \log n)。排序 O(n \log n)DP 遍历 O(n)。- 空间复杂度O(n)。Map 存储 DP 状态最多 2n 个键。