“子段和”的总结
- 最大子段和，用动态规划
- 数组全正数（意味着
presum[]数组递增），可以用滑动窗口 - 数组有负数（意味着
presum[]数组无序），用presum解法- 子段和
>=K、<=K、在范围[lower,upper]，都能用presum解法
- 特例，子段和>=K的最短子段用了单调队列
- 子段和
另：使用presum数组时，k长子段=presum[i]-presum[i-k]一定是半开半闭
- 如果设
presum[i]=[0..i)（这时i也是区间长度），后开，k长子段也是后开（前闭） - 如果设
presum[i]=[0..i]（这时空区间要单独对待），后闭，k长子段也是后闭（前开）