D
DevExCode

LeetCode 1425: Constrained Subsequence Sum Solution

Master LeetCode problem 1425 (Constrained Subsequence Sum), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming with a deque (double-ended queue) to keep track of the maximum subsequence sum ending at each index. We iterate over the array and at each step, we maintain a deque where the front of the deque contains the maximum sum subsequence within the window size k.

  1. Initialize an array dp to store the maximum subsequence sum ending at each index.
  2. Initialize a deque deque to maintain the maximum sum subsequence within the window size k.
  3. Iterate over the input array nums:
    • Remove elements from the front of the deque that are outside the window (i - deque.peekFirst() > k).
    • Update dp[i] as the maximum between the current element nums[i] and the maximum sum subsequence ending before index i (deque.peekFirst()).
    • Add dp[i] to the deque in a decreasing order.
  4. Return the maximum value in the dp array.

Solution Code

import java.util.ArrayDeque;

class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (!deque.isEmpty() && i - deque.peekFirst() > k) {
                deque.pollFirst();
            }
            dp[i] = nums[i] + (deque.isEmpty() ? 0 : Math.max(0, dp[deque.peekFirst()]));
            while (!deque.isEmpty() && dp[i] >= dp[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            maxSum = Math.max(maxSum, dp[i]);
        }
        
        return maxSum;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1425 (Constrained Subsequence Sum)?

This page provides optimized solutions for LeetCode problem 1425 (Constrained Subsequence Sum) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1425 (Constrained Subsequence Sum)?

The time complexity for LeetCode 1425 (Constrained Subsequence Sum) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1425 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1425 in Java, C++, or Python.

Back to LeetCode Solutions