Kimi k2.6 LeetCode 3041. 修改数组后最大化数组中的连续元素数目 JavaScript实现
这道题的核心思路是 排序 + 动态规划。
思路分析
1. 排序：先将数组排序，方便处理连续关系。
2. 动态规划：设 `dp[v]` 表示以值 `v` 结尾的最长连续序列长度。对于每个元素 `x`：
- 不变：值为 `x`，需要前面有以 `x-1` 结尾的序列 → `dp[x] = dp[x-1] + 1`
- +1：值为 `x+1`，需要前面有以 `x` 结尾的序列 → `dp[x+1] = dp[x] + 1`
3. 处理顺序：排序后按顺序处理，对于重复元素，后处理的可以基于前面已更新的状态。
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) {
// 选项1：x 不变，以 x 结尾
const len1 = (dp.get(x - 1) || 0) + 1;
// 选项2：x + 1，以 x+1 结尾
// 注意这里 dp.get(x) 可能已经被当前轮次前面相同元素更新过
const len2 = (dp.get(x) || 0) + 1;
// 更新 dp[x]（不变的情况）
dp.set(x, Math.max(dp.get(x) || 0, len1));
// 更新 dp[x+1]（+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;
};
```
验证示例
示例 1：`nums = [2,1,5,1,1]`
- 排序后：`[1,1,1,2,5]`
- 处理 `1`：`dp[1]=1`, `dp[2]=1`, `res=1`
- 处理第二个 `1`：`dp[1]=1`, `dp[2]=max(1, 1+1)=2`, `res=2`
- 处理第三个 `1`：`dp[1]=1`, `dp[2]=max(2, 1+1)=2`, `res=2`
- 处理 `2`：`dp[2]=max(2, dp[1]+1=2)=2`, `dp[3]=dp[2]+1=3`, `res=3`
- 处理 `5`：`dp[5]=1`, `dp[6]=1`, `res=3`
- 结果：`3` ✓
示例 2：`nums = [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 个键。