What is the brute force approach and complexity for Constrained Subsequence Sum?

dp[i] = nums[i] + max(0, best of the last k dp values), found by a loop with time complexity O(N · K) and space complexity O(N).

What is the optimal approach and complexity for Constrained Subsequence Sum?

Deque of indices with decreasing dp; dp[i] = nums[i] + max(0, dp[front]) with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Constrained Subsequence Sum?

Look for key signals in the prompt: "subsequence … j − i ≤ k" indicates The previous pick is within the last k positions → dp[i] looks at a window of k dp values.; "largest possible sum" indicates We need the **max** of that window → sliding window maximum over dp.; "non-empty, can start and end anywhere" indicates Start fresh is allowed (`max(0, …)`) and the answer is the max over all dp, not the last one..

Constrained Subsequence Sum

Hard·LeetCode #1425 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You are given an integer array nums and a number k.

Pick a non-empty subsequence of nums (some elements, kept in their original order). There is one rule: for any two elements you pick next to each other in the subsequence, at positions i < j, the gap must be small: j − i ≤ k. In other words, you may never skip more than k − 1 elements in a row between two picks.

Return the largest possible sum of such a subsequence. It can start and end anywhere.

Input

An integer array nums of length n, and an integer k.

Output

A single integer: the maximum sum.

Example 1

Input: nums = [10, 2, -10, 5, 20], k = 2

Output: 37

Pick [10, 2, 5, 20]. Skipping -10 makes a gap of 2 (from index 1 to 3), which is allowed.

Example 2

Input: nums = [-1, -2, -3], k = 1

Output: -1

The subsequence can't be empty. The best you can do is pick just -1.

Example 3

Input: nums = [10, -2, -10, -5, 20], k = 2

Output: 23

Pick [10, -2, -5, 20]. You have to keep -2 and -5 to get from 10 to 20 without a gap bigger than 2.

Constraints

• 1 ≤ k ≤ n ≤ 10^5
• −10^4 ≤ nums[i] ≤ 10^4

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“subsequence … j − i ≤ k”

→ The previous pick is within the last k positions → dp[i] looks at a window of k dp values.

“largest possible sum”

→ We need the **max** of that window → sliding window maximum over dp.

“non-empty, can start and end anywhere”

→ Start fresh is allowed (`max(0, …)`) and the answer is the max over all dp, not the last one.

Approach Complexity Ladder

Brute Force — DP checking all k previous indicesO(N · K)O(N)

dp[i] = nums[i] + max(0, best of the last k dp values), found by a loop

Better — max-heap with lazy removalO(N log N)O(N)

Keep (dp, index) in a max-heap; skip tops that are too far back

Optimal — monotonic deque over dpO(N)O(N)

Deque of indices with decreasing dp; dp[i] = nums[i] + max(0, dp[front])

Brute Force Intuition

Fill dp left to right. For each i, loop over the last k indices to find the best dp[j], take max(0, that), and add nums[i]. The answer is the largest dp[i].

Recognition rule for this sub-pattern:

dp[i] needs the best value among the last K states. Keep those candidates in a monotonic deque.

Remember this · Monotonic Stack

Trigger

Next/previous greater or smaller element, spans, histogram areas, "for each element, how far does it dominate?"

Think

When a new element arrives, which older elements can never be the answer again?

Key question

Is my stack increasing or decreasing, and what do I record when I pop?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Monotonic Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Undo / Redo Framework (Command Pattern)

State snapshot management and history stack unwinding.

Explore Track

C++ Internals

Move Semantics & Rvalue References

Eliminating deep copies when pushing and popping complex objects on stacks.

Explore Track

Jump Game VI Shortest Subarray with Sum at Least K