DeepSeek LeetCode 1425.带限制的子序列和 public int constrainedSubsetSum(int[] nums, int k)

以下是 LeetCode 1425「带限制的子序列和」的 Java 解法，使用动态规划 + 单调队列实现，时间复杂度 O(n)，空间复杂度 O(n)。

```java
public int constrainedSubsetSum(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n]; // dp[i] 表示以 i 结尾的子序列的最大和
Deque<Integer> dq = new ArrayDeque<>(); // 单调队列存储索引，按 dp 值递减
int ans = Integer.MIN_VALUE;

for (int i = 0; i < n; i++) {
// 移除窗口外的索引
while (!dq.isEmpty() && dq.peekFirst() < i - k) {
dq.pollFirst();
}
// 获取前 k 个位置的最大 dp 值（负数则取 0）
int maxPrev = dq.isEmpty() ? 0 : Math.max(0, dp[dq.peekFirst()]);
dp[i] = nums[i] + maxPrev;
ans = Math.max(ans, dp[i]);

// 维护单调递减队列
while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) {
dq.pollLast();
}
dq.offerLast(i);
}
return ans;
}
```

算法思路：

· 定义 dp[i] 为必须选择 nums[i] 时，以 i 结尾的子序列的最大和。
· 转移方程：dp[i] = nums[i] + max(0, max(dp[j]))，其中 i - k ≤ j < i。
· 使用单调递减队列维护窗口内 dp 值，队首即为窗口内最大 dp 值。
· 最终答案取所有 dp[i] 的最大值。

注意事项：

· 允许子序列只包含当前元素（即不加任何前面的元素），因此 maxPrev 需要与 0 比较。
· 若所有数均为负数，答案即为最大元素（因为只选一个元素的情况会被考虑）。