follow up 239 Deque: double-ended queue
/* ⭐️
Time O(N). Because all element are pushed and popped at most once.
Space O(K). Because at most O(K) elements in the deque.
Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].
dp[3] = dp[1] + nums[3] rather than dp[2] + nums[i];
edge case: int res = nums[0]; 面试应该问清楚
Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subsequence must be non-empty, so we choose the largest number.
Input: nums = [-5266,4019,7336,-3681,-5767], k = 2
Output: -1
Explanation: Must consider the first element is a huge negative value.
if(dp[i] > 0)
deque.offer(dp[i]);
*/
class Solution {
public int constrainedSubsetSum(int[] nums, int k) {
int len = nums.length;
if(nums == null || len * k == 0) return -1;
int[] dp = new int[nums.length];
Deque<Integer> deque = new ArrayDeque<>();
// The subsequence must be non-empty, so we choose the largest number.
int res = nums[0];
for(int i = 0; i < len; i++) {
dp[i] += !deque.isEmpty() ? nums[i] + deque.getFirst() : nums[i];
res = Math.max(dp[i], res);
while(!deque.isEmpty() && deque.getLast() < dp[i]) {
deque.pollLast();
}
// Consider for i = 0 && nums[i] < 0
// All element is negative values.
if(dp[i] > 0)
deque.offer(dp[i]);
if(i >= k && !deque.isEmpty() && deque.getFirst() == dp[i - k])
deque.pollFirst();
}
return res;
}
}