1425. Constrained Subsequence Sum

HardQueueArrayDynamic ProgrammingSliding WindowMonotonic QueueHeap (Priority Queue)
Leetcode Link

Problem Description

Given an integer array nums and an integer k, you are tasked with finding the maximum sum of a non-empty subsequence within the array. A subsequence here is defined as a sequence that can be derived from the array by deleting some elements without changing the order of the remaining elements. However, there's an additional constraint with regard to the subsequence. For any two consecutive integers in the subsequence, say nums[i] and nums[j] where i < j, the difference between the indices j - i must be less than or equal to k.

In simplified terms, you need to choose a subsequence such that any two adjacent numbers in this subsequence are not more than k positions apart in the original array, and the sum of this subsequence is as large as possible.

Intuition

To arrive at the solution, consider two important aspects: dynamic programming (DP) for keeping track of the subsequences and a 'sliding window' to enforce the constraint of the elements being within a distance k of each other.

With dynamic programming, create an array dp where each dp[i] stores the maximum sum of the subsequence up to the i-th element by following the constraint. To maintain the k distance constraint, use a deque (double-ended queue) that acts like a sliding window, carrying indices of elements that are potential candidates for the maximum sum. At each step:

  • Remove indices from the front of the deque which are out of the current window of size k.
  • Calculate dp[i] by adding the current element nums[i] to the max sum of the window (which is dp[q[0]], q being the deque). If there are no elements in q, just take the current element nums[i].
  • Since we want to maintain a decreasing order of dp values in the deque to quickly access the maximum sum, remove elements from the end of the deque which have a dp value less than or equal to the current dp[i].
  • Add the current index i to the deque.
  • Update the answer with the maximum dp[i] seen so far.

This approach ensures that the deque always contains indices whose dp values form a decreasing sequence, and thus the front of the deque gives us the maximum sum for the current window, while satisfying the distance constraint.

Learn more about Queue, Dynamic Programming, Sliding Window, Monotonic Queue and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which two pointer techniques do you use to check if a string is a palindrome?

Solution Approach

The implementation uses dynamic programming in combination with a deque to efficiently solve the problem by remembering previous results and ensuring that the constraint is maintained.

The initial setup involves creating a DP table as a list dp of size n (the length of nums) and initializing an answer variable ans to negative infinity to keep track of the maximum subsequence sum found so far.

Here is a step-by-step walkthrough of the implementation:

  1. Iterate over the array nums using the index i and the value v. This loop will determine the dp[i] value for each element in nums.

  2. If the deque q has elements and the oldest element's index in the deque (q[0]) is out of the window (i.e., i - q[0] > k), pop it from the front of the deque.

  3. Set dp[i] to the maximum of 0 and the sum of the value v added to dp[q[0]] (the maximum sum within the window). If q is empty, just add v to 0. This step ensures that we do not consider subsequences with negative sums since they would decrease the overall maximum sum we are trying to compute.

  4. While the deque has elements and the last element in the deque has a dp value less than or equal to dp[i] (since dp[i] now holds the maximum sum up to i), pop elements from the end of the deque. This maintains the invariant that the deque holds indices in decreasing order of their dp values.

  5. Append the current index i to the deque.

  6. Update ans with the maximum value between ans and dp[i] to update the global maximum sum each time dp[i] is calculated.

  7. Once the iteration over nums is complete, ans will contain the maximum sum of a subsequence satisfying the given constraint, so return ans.

This algorithm makes use of the following patterns and data structures:

  • Dynamic Programming: By storing and reusing solutions to subproblems (dp[i]), we solve larger problems efficiently.
  • Monotonic Queue (Deque): A deque allows us to efficiently track the "window" of elements that are within k distance from the current element while simultaneously maintaining a monotonically decreasing order of dp values.
  • Sliding Window Technique: The concept of having a window moving through the data while maintaining certain conditions (here, a maximum sum within a distance k) is a classic example of this technique.
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

Example Walkthrough

Let's assume we have an integer array nums = [10, 2, -10, 5, 20] and k = 2, and we want to find the maximum sum of a non-empty subsequence such that consecutive elements in the subsequence are not more than k positions apart in the original array.

We initialize our dp and ans:

  • dp = [0, 0, 0, 0, 0] with the same length as nums
  • ans = -โˆž (minimum possible value)

We start by iterating over nums:

  1. For i = 0, v = 10. The deque q is empty, so dp[0] = 10 and q = [0]. Now ans = 10.
  2. For i = 1, v = 2. Since q[0] is 0 and i - q[0] = 1 which is within the range k, we calculate dp[1] = max(dp[q[0]] + v, v) = max(10 + 2, 2) = 12. Now q = [0, 1] after cleaning outnumbers by dp value (no changes in this step), and ans = 12.
  3. For i = 2, v = -10. Since i - q[0] = 2 which is within k, we calculate dp[2] = max(dp[q[0]] + v, v) = max(12 - 10, -10) but here both options are negative, so dp[2] = 0. We then remove from q since dp[1] > dp[2]. Now q = [1] and ans = 12.
  4. For i = 3, v = 5. Since i - q[0] = 2 which is equal to k, we can use q[0]. Thus, dp[3] = max(dp[q[0]] + v, v) = max(12 + 5, 5) = 17 and q = [1, 3]. We update ans = 17 now.
  5. For i = 4, v = 20. Here, we first remove q[0] because i - q[0] = 3 which is greater than k, leaving q = [3]. We then calculate dp[4] = dp[q[0]] + v = 17 + 20 = 37, so q = [4] after removing q[0] because dp[3] < dp[4]. ans is updated to 37.

After iterating through the loop, we've looked at all possible subsequences that obey the k limit rule. The maximum subsequence sum is stored in ans which is 37.

To summarize this walk-through:

  • We used DP to remember the maximum subsequence sums for subarrays.
  • We maintained a deque q to ensure elements are within k distance in the subsequence.
  • We updated ans at every step with the maximum value of dp[i].
  • At the end of the loop, ans gave us the maximum sum possible under the given constraints.

Solution Implementation

1from collections import deque
2from typing import List
3
4class Solution:
5    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
6        # The number of elements in nums
7        n = len(nums)
8
9        # Initialize a list(dp) to store the maximum subset sum ending at each index
10        dp = [0] * n
11
12        # Initializing the answer to negative infinity to handle negative numbers
13        max_sum = float('-inf')
14
15        # A deque to keep the indexes of useful elements in our window of size k
16        q = deque()
17
18        # Loop through each number in nums
19        for i, value in enumerate(nums):
20            # If the first element of deque is out of the window of size k, remove it
21            if q and i - q[0] > k:
22                q.popleft()
23
24            # Calculate the max subset sum at this index as the greater of 0 or the sum at the top of the deque plus the current value
25            dp[i] = max(0, dp[q[0]] if q else 0) + value
26
27            # Pop elements from deque if they have a smaller subset sum than dp[i],
28            # because they are not useful for future calculations
29            while q and dp[q[-1]] <= dp[i]:
30                q.pop()
31
32            # Append the current index to the deque
33            q.append(i)
34
35            # Update the maximum answer so far with the current dp value
36            max_sum = max(max_sum, dp[i])
37
38        # Return the maximum subset sum found
39        return max_sum
40
1class Solution {
2    public int constrainedSubsetSum(int[] nums, int k) {
3        // Length of the input array
4        int n = nums.length;
5      
6        // Dynamic programming array to store the maximum subset sum
7        // ending with nums[i]
8        int[] dp = new int[n];
9      
10        // Initialize the answer with the smallest possible integer
11        int answer = Integer.MIN_VALUE;
12      
13        // Declaring a deque to store indices of useful elements in dp array
14        Deque<Integer> queue = new ArrayDeque<>();
15      
16        // Loop through each number in the input array
17        for (int i = 0; i < n; ++i) {
18            // Remove indices of elements which are out of the current sliding window
19            if (!queue.isEmpty() && i - queue.peek() > k) {
20                queue.poll();
21            }
22          
23            // Calculate dp[i] by adding current number to the maximum of 0 or
24            // the element at the front of the queue, which represents the maximum sum
25            // within the sliding window
26            dp[i] = Math.max(0, queue.isEmpty() ? 0 : dp[queue.peek()]) + nums[i];
27          
28            // Remove indices from the back of the queue where the dp value is less than dp[i]
29            // to maintain the decreasing order of dp values in the queue
30            while (!queue.isEmpty() && dp[queue.peekLast()] <= dp[i]) {
31                queue.pollLast();
32            }
33          
34            // Offer the current index to the queue
35            queue.offer(i);
36          
37            // Update the answer with the maximum value of dp[i] so far
38            answer = Math.max(answer, dp[i]);
39        }
40      
41        // Return the maximum sum as answer
42        return answer;
43    }
44}
45
1class Solution {
2public:
3    int constrainedSubsetSum(vector<int>& nums, int k) {
4        // Get the size of the input vector nums.
5        int n = nums.size();
6        // Create a DP array to store the maximum subset sums at each position.
7        vector<int> dp(n);
8        // Initialize the answer variable with the minimum possible integer value.
9        int maxSubsetSum = INT_MIN;
10        // Initialize a double-ended queue to maintain the window of elements.
11        deque<int> window;
12
13        // Iterate over the elements in nums.
14        for (int i = 0; i < n; ++i) {
15            // If the window front is out of the allowed range [i-k, i], remove it.
16            if (!window.empty() && i - window.front() > k) {
17                window.pop_front();
18            }
19            // Compute the maximum subset sum at the current index i.
20            // It is the maximum sum of the previous subset sum (if not empty) and the current number.
21            dp[i] = max(0, window.empty() ? 0 : dp[window.front()]) + nums[i];
22            // Update the overall maximum subset sum.
23            maxSubsetSum = max(maxSubsetSum, dp[i]);
24            // Maintain the window such that its elements are in decreasing order of their dp values.
25            while (!window.empty() && dp[window.back()] <= dp[i]) {
26                window.pop_back();
27            }
28            // Add the current index to the window.
29            window.push_back(i);
30        }
31        // Return the maximum subset sum.
32        return maxSubsetSum;
33    }
34};
35
1// Define type alias for easy reference
2type Deque = number[];
3
4// Initialize a deque to maintain the window of elements
5let window: Deque = [];
6
7// Function to calculate the constrained subset sum
8function constrainedSubsetSum(nums: number[], k: number): number {
9    // Get the size of the input array `nums`
10    const n = nums.length;
11    // Create an array to store the maximum subset sums at each position
12    const dp: number[] = new Array(n);
13    // Initialize the answer variable with the minimum possible number value
14    let maxSubsetSum = Number.MIN_SAFE_INTEGER;
15
16    // Iterate over the elements in `nums`
17    for (let i = 0; i < n; ++i) {
18        // If the window front is out of the allowed range [i-k, i], remove it
19        if (window.length !== 0 && i - window[0] > k) {
20            window.shift();
21        }
22        // Compute the maximum subset sum at the current index `i`
23        // It is the max of 0 (to avoid negative sums) and the subset sum of the front of the window
24        dp[i] = Math.max((window.length === 0 ? 0 : dp[window[0]]), 0) + nums[i];
25        // Update the overall maximum subset sum
26        maxSubsetSum = Math.max(maxSubsetSum, dp[i]);
27        // Maintain the window such that its elements are in decreasing order of their dp values
28        while (window.length !== 0 && dp[window[window.length - 1]] <= dp[i]) {
29            window.pop();
30        }
31        // Add the current index to the window
32        window.push(i);
33    }
34    // Return the maximum subset sum
35    return maxSubsetSum;
36}
37
38// Example usage:
39// let result = constrainedSubsetSum([10, 2, -10, 5, 20], 2);
40// console.log(result); // Output will be the maximum constrained subset sum.
41
Not Sure What to Study? Take the 2-min Quiz๏ผš

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Time and Space Complexity

The given Python code defines a function constrainedSubsetSum which calculates the maximum sum of a non-empty subsequence of the array nums, where the subsequence satisfies the constraint that no two elements are farther apart than k in the original array.

Time Complexity

The time complexity of the code is O(n), where n is the number of elements in the array nums. This is because the algorithm iterates over each element exactly once. Inside the loop, it performs operations that are constant time on average, such as adding or removing elements from the deque q. The deque maintains the maximum sum at each position within the window of k, and the operations are done in constant time due to the nature of the double-ended queue.

Even though we have a while-loop inside the for-loop that pops elements from the deque, this does not increase the overall time complexity. Each element is added once and removed at most once from the deque, leading to an average constant time for these operations per element.

Space Complexity

The space complexity of the code is O(n), where n is the size of nums. This is because the algorithm allocates an array dp of the same size as nums to store the maximum sum up to each index. Furthermore, the deque q can at most contain k elements, where k is the constraint on the distance between the elements in the subsequence. However, since k is a constant with respect to n, the primary factor that affects the space complexity is the dp array.

In summary:

  • Time complexity is O(n).
  • Space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the minimum element can be found in:

Recommended Readings

Queue Intro

Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Sliding Window Maximum

https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ