# Monotonic Queue in DP

## Summary

In this post, I will introduce some DP problems involving the Monotonic Queue.

## Details

#### LC 1425. Constrained Subset Sum

It is not difficult to get the following `O(n^2)` solution.

``alg[i] = nums[i] + max {alg[i+j] for j=[1, k]}``

However, the complexity is not good. What we need for `{alg[i+j] for j=[1, k]}` is only the maximum. So we need to keep tracking the sliding window maximum. An `O(nlogn)` solution is intuitive.

``````alg[i] = nums[i] + pq.max
// note that we need to invalidate pq when the index_of_max > i + k``````

It is still not enough. Monotonic Queue works perfect for Sliding Window Maximum.

``alg[i] = nums[i] + max(0, alg[mq.sliding_window_max()])``

#### LC 1340. Jump Game V

It is not difficult to get the following `O(n^2)` solution.

``````alg[i] = max {
1 + alg[k] for k in [i - d, i + d]
}``````

However, the time complexity could be reduced to `O(n)`. We think backwards. For each index `i`, it could be reached by indexes that values are larger. We greedily choose the nearest higher since it leaves more indexes for the rest jumps. Monotonic Queues work perfectly for Sliding Window Nearest Higher Number.

``````alg[i] = 1 + max{
alg[left_nearest_higher[i]],
alg[right_nearest_higher[i]]
}``````