What signals in a problem statement indicate the Monotonic deque for DP sub-pattern?

"you can jump at most k steps"; "consecutive chosen indices at most k apart"; a DP whose transition is `max(dp[i − k … i − 1])`; O(N·k) DP that times out

Monotonic deque for DP (Monotonic Stack Sub-pattern)

Q: What makes Monotonic deque for DP different from other sub-patterns?

**Jump Game VI**: `dp[i] = nums[i] + max of the window`. **Constrained Subsequence Sum**: same, but you may also start fresh, so add `max(0, window max)` and the answer is the max of all `dp`. **Shortest Subarray with Sum at Least K** (linked from Sliding Window) keeps an increasing deque of prefix sums instead. A max-heap with lazy deletion is the O(N log N) stepping stone to all three.

When dp[i] depends on the best dp value among the last k states, keep those candidates in a monotonic deque: the front is the best, the back loses to newer, better states.

Signals in the problem statement

›
"you can jump at most k steps"
›
"consecutive chosen indices at most k apart"
›
a DP whose transition is max(dp[i − k … i − 1])
›
O(N·k) DP that times out

What makes it different

Jump Game VI: dp[i] = nums[i] + max of the window. Constrained Subsequence Sum: same, but you may also start fresh, so add max(0, window max) and the answer is the max of all dp. Shortest Subarray with Sum at Least K (linked from Sliding Window) keeps an increasing deque of prefix sums instead. A max-heap with lazy deletion is the O(N log N) stepping stone to all three.

Questions

ordered from “learn the idea” to “recognise it without help”

1
Jump Game VI
Basic Anchor·LeetCode #1696
WalkthroughMedium
2
Constrained Subsequence Sum
Pattern Transfer·LeetCode #1425
WalkthroughHard
3
Shortest Subarray with Sum at Least K
Tricky / Edge Case·LeetCode #862
WalkthroughHard

Template

deque-dp-template.cpp

// Jump Game VI: dp[i] = nums[i] + max(dp[i-k .. i-1]). Deque of indices, dp decreasing.
int maxResult(vector<int>& nums, int k) {
    int n = nums.size();
    vector<long long> dp(n);
    deque<int> dq;
    dp[0] = nums[0];
    dq.push_back(0);
    for (int i = 1; i < n; i++) {
        if (dq.front() < i - k) dq.pop_front();      // left the window (one per step)
        dp[i] = nums[i] + dp[dq.front()];            // front = best of the last k
        while (!dq.empty() && dp[dq.back()] <= dp[i])
            dq.pop_back();                           // older AND not better: never needed
        dq.push_back(i);
    }
    return dp[n - 1];
}

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?

Span / dominance