题目大意：
带限制的子序列和
给你一个整数数组 nums 和一个整数 k ，请你返回 非空 子序列元素和的最大值，子序列需要满足：子序列中每两个 相邻 的整数 nums[i] 和 nums[j] ，它们在原数组中的下标 i 和 j 满足 i < j 且 j – i <= k 。
数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。
示例 1：
输入：nums = [10,2,-10,5,20], k = 2 输出：37 解释：子序列为 [10, 2, 5, 20] 。
示例 2：
输入：nums = [-1,-2,-3], k = 1 输出：-1 解释：子序列必须是非空的，所以我们选择最大的数字。
示例 3：
输入：nums = [10,-2,-10,-5,20], k = 2 输出：23 解释：子序列为 [10, -2, -5, 20] 。
提示：
1 <= k <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1425
解题思路分析：
本周的状态非常糟糕，周赛时，两道中等题在提交时共发生了3次提交错误，导致被罚30分钟，并且在连续提交错误之后，心态上也发生了一些变化，以至于在做最后一题时产生了一些厌烦情绪，这也是我今后需要改进的地方。
回到本题，这是本周周赛的压轴Hard级别题目，简单来说就是求一个数组中和最大的子序列。在不考虑子序列条件限制的情况下，和最大的一定是数组中所有正数组成的子序列。但是题目要求，子序列中相邻的两个元素在原数组中的下标差不能大于k，这就意味着我们要想得到符合条件最大子序列的话，那么该子序列中可能会掺入一些负数。
解题时，我们可以将原数组想象成为N个部分（子数组），其中每一个部分都是连续的正数（大于等于0），或者连续的负数。我们首先重点关注一下负数的部分，如果某一个负数子数组的长度小于等于k，那么我们可以将这一部分直接忽略掉。反之如果该负数子数组的长度大于k，那么，我们需要使用一个优先队列（PriorityQueue），从子数组首位开始向后循环，顺序向队列中添加这些负数，当队列的长度等于k时，我们从队列中取出一个最大值，将它作为子序列的一个对象，并将循环的下标设置为该对象所在下标，清空队列，继续重复上述操作，直到循环至子数组尾部为止。这样就能保证取出一些最大的负数（最小代价）来保证两个正数子数组相连通。
通过上述的操作，我们实际上可以得到类似以下这样的一个子序列：
[连续正数],(0或多个负数),[连续正数],(0或多个负数),[连续正数]....
上述序列实际上就是符合条件的一个子序列，但它并非是和最大的子序列，那么和最大的子序列一定是上述序列的某个子数组，因此问题就转化为在一个数组中找到和最大的子数组问题。这个问题的算法我们在之前的文章中多次提到过，简单来说，我们从第一位开始向后循环，利用一个sum对象来累加遍历过的所有数字和，并使用一个maxSum对象来记录最大sum，另外，如果当前数字加上sum之后反而比当前数字更小的话，那么不如舍弃之前的数字，将区间开始坐标设置为当前位置。这样遍历完整个数组，就能得到最大区间sum。也就是本题的解。
实现代码：
public int constrainedSubsetSum(int[] nums, int k) {
// 存储连续负数的Queue
PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->b[0]-a[0]);
// 当前区间和
int sum=0;
// 最大区间和
int masSum=Integer.MIN_VALUE;
// 遍历每一个数字
for(int i=0;i<nums.length;i++){
// 如果当前数字大于等于0
if(nums[i]>=0){
// 将当前数字累加至sum
sum+=nums[i];
// 如果当前数字大于sum，舍弃之前的数字，将sum设为当前数字
if(nums[i]>sum) sum=nums[i];
// 更新最大区间和
masSum=Math.max(sum, masSum);
// 清理Queue
q.clear();
} else{ // 当前数字小于0
// 将当前数字和下标加入Queue
q.offer(new int[]{nums[i],i});
// 如果Queue的大小等于k，
// 说明我们需要在当前的连续k个数中选择一个数字，
// 来确保子序列每两个相邻元素之间的下标小于等于k
if(q.size()==k){
// 取出Queue中最大的负数元素
int[] item=q.poll();
i=item[1]; // 将循环下标设置为当前元素下标
sum+=item[0]; // 累加当前元素至sum
// 如果当前数字大于sum，舍弃之前的数字，将sum设为当前数字
if(item[0]>sum) sum=item[0];
// 更新最大区间和
masSum=Math.max(sum, masSum);
q.clear(); // 清空Queue
}
}
}
return masSum;
} 本题解法执行时间为9ms。
Runtime: 9 ms, faster than 96.77% of Java online submissions for Constrained Subset Sum.
Memory Usage: 48.5 MB, less than 100.00% of Java online submissions for Constrained Subset Sum.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1425-constrained-subset-sum解题思路分析/