Section Recap

You learned monotonic queue improvement for DP:

$1.$ Recognize sliding window min/max in DP transitions.

$2.$ Use decreasing deque for max, increasing deque for min.

$3.$ Remove expired indices from front, dominated indices from back.

$4.$ Each element enters and exits once, giving $O(n)$ total time. You solved four problems: Sliding Window Maximum (foundation), Jump Game VI (basic DP), Constrained Subsequence Sum (optional inclusion), and Shortest Subarray (prefix sums). You now have a effective $O(nk) \to O(n)$ improvement technique.