JunyiCode
5/2/2020 - 8:33 PM

1425. Constrained Subsequence Sum

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;
    }
}