【算法提高课】动态规划笔记

单调队列优化DP

1. 可以开个结构体存下标和值，不用只存下标，不容易写错；
2. 此类问题一般都有烦人的边界问题，需要细心处理；
3. 单调队列可以换成优先队列，复杂度会多个\(log\)。
4. 推出式子之后一定要弄清楚哪个才是维护的最值，比如维护的前缀和的最值，入队的却是原数组的值，等等。

• 135. 最大子序和 因为子序列是连续的，设\(f[i]\)为以\(i\)结尾的所有子序列中和的最大值（因为子序列长度至少是\(1\)，所以肯定要选\(i\)）。\(f[i]=max(w[i], w[i]+w[i-1], w[i]+...+w[i-m+1])\)。转换成前缀和\(s\)就是\(f[i]=max(s[i]-s[i-1], s[i]-s[i-2], s[i]-s[i-m])=s[i]+max(-s[j])(j \in [i-m, i-1])\)。使用单调队列维护\(max(-s[j])\)即可。