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.

Description Hints 4 Solution Video 20:52

1425. Constrained Subsequence Sum

Hard56.5% acceptance2 companies

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 <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Asked at 2 companies

Akuna Capital

Google

Topics

Hints open one at a time

Hint 1

Use dynamic programming.

Hint 2

Let dp[i] be the solution for the prefix of the array that ends at index i, if the element at index i is in the subsequence.

Hint 3

dp[i] = nums[i] + max(0, dp[i-k], dp[i-k+1], ..., dp[i-1])

Hint 4

Use a heap with the sliding window technique to optimize the dp.

20:52

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution