1425. Constrained Subsequence Sum
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 elementnums[i]
to the max sum of the window (which isdp[q[0]]
, q being the deque). If there are no elements inq
, just take the current elementnums[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 adp
value less than or equal to the currentdp[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.
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:
-
Iterate over the array
nums
using the indexi
and the valuev
. This loop will determine thedp[i]
value for each element innums
. -
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. -
Set
dp[i]
to the maximum of 0 and the sum of the valuev
added todp[q[0]]
(the maximum sum within the window). Ifq
is empty, just addv
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. -
While the deque has elements and the last element in the deque has a
dp
value less than or equal todp[i]
(sincedp[i]
now holds the maximum sum up toi
), pop elements from the end of the deque. This maintains the invariant that the deque holds indices in decreasing order of theirdp
values. -
Append the current index
i
to the deque. -
Update
ans
with the maximum value betweenans
anddp[i]
to update the global maximum sum each timedp[i]
is calculated. -
Once the iteration over
nums
is complete,ans
will contain the maximum sum of a subsequence satisfying the given constraint, so returnans
.
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 ofdp
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 asnums
ans = -∞
(minimum possible value)
We start by iterating over nums
:
- For
i = 0
,v = 10
. The dequeq
is empty, sodp[0] = 10
andq = [0]
. Nowans = 10
. - For
i = 1
,v = 2
. Sinceq[0]
is0
andi - q[0] = 1
which is within the rangek
, we calculatedp[1] = max(dp[q[0]] + v, v) = max(10 + 2, 2) = 12
. Nowq = [0, 1]
after cleaning outnumbers bydp
value (no changes in this step), andans = 12
. - For
i = 2
,v = -10
. Sincei - q[0] = 2
which is withink
, we calculatedp[2] = max(dp[q[0]] + v, v) = max(12 - 10, -10)
but here both options are negative, sodp[2] = 0
. We then remove fromq
sincedp[1] > dp[2]
. Nowq = [1]
andans = 12
. - For
i = 3
,v = 5
. Sincei - q[0] = 2
which is equal tok
, we can useq[0]
. Thus,dp[3] = max(dp[q[0]] + v, v) = max(12 + 5, 5) = 17
andq = [1, 3]
. We updateans = 17
now. - For
i = 4
,v = 20
. Here, we first removeq[0]
becausei - q[0] = 3
which is greater thank
, leavingq = [3]
. We then calculatedp[4] = dp[q[0]] + v = 17 + 20 = 37
, soq = [4]
after removingq[0]
becausedp[3] < dp[4]
.ans
is updated to37
.
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 withink
distance in the subsequence. - We updated
ans
at every step with the maximum value ofdp[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
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.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80]
is 4
and LIS is
[3, 7, 40, 80]
.
What is the recurrence relation?
Recommended Readings
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
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
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 Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.