关于最大字段和
  • 板块学术版
  • 楼主Chinshyo
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/8/13 22:34
  • 上次更新2023/10/27 15:32:30
查看原帖
关于最大字段和
312820
Chinshyo楼主2022/8/13 22:34

我在看线段树题解(算法竞赛进阶指南215页)的时候发现 dpdp 求最大字段和有这样的递推式

tp.dat=max(tlchild.max,trchild.max,trchild.lmax+tlchild.rmax),t_p.dat=max(t_{lchild}.max, t_{rchild}.max,t_{rchild}.lmax+t_{lchild}.rmax),

其中 lmaxlmax 是紧靠左最大字段和，rmaxrmax是紧靠右最大字段和

2022/8/13 22:34