Skip to main content
Talentd

Constrained Subsequence Sum - Solution & Explanation

HardArrayDynamic ProgrammingQueueSliding Window23 min readAsked at: Google, Akuna Capital
Practice this problem

Problem Statement

Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of that array such that for every two consecutive integers in the subsequence, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

A subsequence of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

 

Example 1:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

Example 2:

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subsequence must be non-empty, so we choose the largest number.

Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subsequence is [10, -2, -5, 20].

 

Constraints:

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

Approach Overview

Problem Overview: Given an integer array nums and an integer k, choose a subsequence such that the difference between consecutive chosen indices is at most k. The goal is to maximize the subsequence sum.

Approach 1: Dynamic Programming (Brute Window Scan) (Time: O(nk), Space: O(n))

Define dp[i] as the maximum subsequence sum that ends at index i. To compute it, look at the previous k positions and extend the best subsequence: dp[i] = nums[i] + max(0, dp[i-k...i-1]). This requires scanning up to k elements for every index. The approach demonstrates the core dynamic programming transition but becomes slow when k is large because every step performs a window maximum search.

Approach 2: Dynamic Programming with Priority Queue (Heap) (Time: O(n log k), Space: O(n))

Replace the repeated window scan with a max heap storing pairs (dp value, index). While iterating through the array, remove heap entries whose index is more than k behind the current position. The heap top always gives the largest valid dp value within the window. Compute dp[i] = nums[i] + max(0, top), then push the new state back into the heap. This reduces the lookup cost to log k while maintaining the sliding window constraint.

Approach 3: Dynamic Programming with Sliding Window Maximum (Monotonic Deque) (Time: O(n), Space: O(n))

The optimal approach maintains the window maximum using a monotonic deque. Store indices of dp values in decreasing order so the front always holds the maximum candidate. Before processing index i, remove indices outside the k window. Compute dp[i] = nums[i] + max(0, dp[deque front]). After computing dp[i], remove smaller values from the back of the deque to preserve decreasing order and push i. Each index enters and leaves the deque once, producing linear time. This technique combines dynamic programming with a sliding window maximum implemented using a monotonic queue.

Recommended for interviews: Interviewers typically expect the monotonic deque solution with O(n) time. Explaining the dp[i] = nums[i] + max(0, best previous) transition first shows understanding of the problem. Improving the window maximum using a deque demonstrates strong knowledge of sliding window optimization and queue-based data structures.

Approach 1: Dynamic Programming with Sliding Window Maximum

This approach involves using dynamic programming with a sliding window to maintain the maximum sum at each position. For each position i in the array, calculate the maximum sum that can be achieved till that position, considering the constraint j - i <= k. Use a deque to track the indices which offer the maximum sum within the range of k.

The solution uses a dynamic programming array to store the maximum sum possible up to each index. It utilizes a deque to maintain useful indices that help in calculating the needed maximum sum over the moving window of size k without having to recompute every time.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in the array nums. The space complexity is O(n) due to the storage of the dp array and deque.

Try this approach in the editor →

Approach 2: Dynamic Programming with Priority Queue (Heap)

By using a priority queue (or heap), we manage the maximum possible sum within the constraint more efficiently. We employ dynamic programming to calculate the possible maximal sum at each index while maintaining a priority queue to keep track of the relevant maximum sums.

C implementation utilizes a priority queue structure to keep maximum subsequences track. Through a heap-push and heap-pop approach, the subset with the highest value is computed dynamically across the moving windows.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log k) primarily due to heap operations. Space Complexity: O(n) is utilized by the dp array and the heap.

Try this approach in the editor →

Approach 3: Dynamic Programming + Monotonic Queue

We define f[i] to represent the maximum sum of the subsequence ending at nums[i] that meets the conditions. Initially, f[i] = 0, and the answer is max_{0 leq i \lt n} f(i).

We notice that the problem requires us to maintain the maximum value of a sliding window, which is a typical application scenario for a monotonic queue. We can use a monotonic queue to optimize the dynamic programming transition.

We maintain a monotonic queue q that is decreasing from the front to the back, storing the indices i. Initially, we add a sentinel 0 to the queue.

We traverse i from 0 to n - 1. For each i, we perform the following operations:

  • If the front element q[0] satisfies i - q[0] > k, it means the front element is no longer within the sliding window, and we need to remove the front element from the queue;
  • Then, we calculate f[i] = max(0, f[q[0]]) + nums[i], which means we add nums[i] to the sliding window to get the maximum subsequence sum;
  • Next, we update the answer ans = max(ans, f[i]);
  • Finally, we add i to the back of the queue and maintain the monotonicity of the queue. If f[q[back]] leq f[i], we need to remove the back element until the queue is empty or f[q[back]] > f[i].

The final answer is ans.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Sliding Window Maximum

Time Complexity: O(n), where n is the number of elements in the array nums. The space complexity is O(n) due to the storage of the dp array and deque.

Dynamic Programming with Priority Queue (Heap)

Time Complexity: O(n log k) primarily due to heap operations. Space Complexity: O(n) is utilized by the dp array and the heap.

Dynamic Programming + Monotonic Queue—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Window ScanO(nk)O(n)Conceptual baseline to understand the DP transition
DP with Priority Queue (Heap)O(n log k)O(n)When a heap is easier to implement than a deque
DP with Monotonic Deque (Sliding Window Maximum)O(n)O(n)Optimal solution for large inputs and typical interview expectation

Video Solution

Constrained Subsequence Sum - Leetcode 1425 - Python • NeetCodeIO • 9,804 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Constrained Subsequence Sum easy or hard?
Constrained Subsequence Sum is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the DP transition and optimizing the sliding window maximum using a monotonic deque or heap to avoid O(nk) time.
Constrained Subsequence Sum Python/Java solution
Python and Java implementations typically use dynamic programming with either a deque or a priority queue. The deque-based approach achieves O(n) time by maintaining a decreasing sequence of DP values, while the heap-based approach runs in O(n log k). Both implementations follow the same DP recurrence.
How to solve Constrained Subsequence Sum in O(n)?
Use dynamic programming with a monotonic deque to track the maximum dp value in the previous k positions. For each index i, compute dp[i] = nums[i] + max(0, dp at deque front). Remove indices outside the window and maintain decreasing order by removing smaller values from the back. Each index is processed once, producing linear time.
What is the best approach for Constrained Subsequence Sum?
The optimal approach uses dynamic programming with a monotonic deque to maintain the maximum DP value within the last k indices. Each step computes dp[i] = nums[i] + max(0, best previous dp in window). The deque keeps values in decreasing order so the maximum is always available in O(1). This reduces the overall complexity to O(n) time and O(n) space.
Is Constrained Subsequence Sum asked at Google/Amazon/Meta?
Constrained Subsequence Sum is a common hard dynamic programming interview problem and variations have appeared in interviews at companies like Google, Amazon, and Meta. The question tests DP transitions, sliding window optimization, and data structure knowledge such as heaps or monotonic queues.
What data structure is used in Constrained Subsequence Sum?
The optimal solution uses a monotonic deque (double-ended queue) to maintain the maximum DP value inside a sliding window. Alternative solutions use a max heap or priority queue to track the best candidate within the last k indices.
What is the time complexity of Constrained Subsequence Sum?
The optimal solution runs in O(n) time using a monotonic deque that maintains the maximum DP value within a sliding window of size k. Each element is inserted and removed from the deque at most once. Alternative implementations using a heap take O(n log k) time.

Ready to solve this problem?

Practice Constrained Subsequence Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Element-Sum of a Complete Subset of Indices