# 1425. Constrained Subsequence Sum

• Time: $O(n)$
• Space: $O(k)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public: int constrainedSubsetSum(vector& nums, int k) { // dp[i] := max sum of non-empty subsequence in nums[0..i] vector dp(nums.size()); // Q stores dp[i - k], dp[i - k + 1], ..., dp[i - 1] whose values are > 0 in // Decreasing order deque q; for (int i = 0; i < nums.size(); ++i) { if (q.empty()) dp[i] = nums[i]; else dp[i] = max(q.front(), 0) + nums[i]; while (!q.empty() && q.back() < dp[i]) q.pop_back(); q.push_back(dp[i]); if (i >= k && dp[i - k] == q.front()) q.pop_front(); } return *max_element(begin(dp), end(dp)); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int constrainedSubsetSum(int[] nums, int k) { // dp[i] := max sum of non-empty subsequence in nums[0..i] int[] dp = new int[nums.length]; // Q stores dp[i - k], dp[i - k + 1], ..., dp[i - 1] whose values are > 0 in decreasing order Deque q = new ArrayDeque<>(); for (int i = 0; i < nums.length; ++i) { if (q.isEmpty()) dp[i] = nums[i]; else dp[i] = Math.max(q.peekFirst(), 0) + nums[i]; while (!q.isEmpty() && q.peekLast() < dp[i]) q.pollLast(); q.offerLast(dp[i]); if (i >= k && dp[i - k] == q.peekFirst()) q.pollFirst(); } return Arrays.stream(dp).max().getAsInt(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution: def constrainedSubsetSum(self, nums: List[int], k: int) -> int: # dp[i] := max sum of non-empty subsequence in nums[0..i] dp = [0] * len(nums) # Q stores dp[i - k], dp[i - k + 1], ..., dp[i - 1] whose values are > 0 in decreasing order q = collections.deque() for i, num in enumerate(nums): if q: dp[i] = max(q[0], 0) + num else: dp[i] = num while q and q[-1] < dp[i]: q.pop() q.append(dp[i]) if i >= k and dp[i - k] == q[0]: q.popleft() return max(dp)