关于最长上升子序列优化写法的疑问
  • 板块学术版
  • 楼主lizeyuannb
  • 当前回复16
  • 已保存回复16
  • 发布时间2022/8/3 17:32
  • 上次更新2023/10/27 17:11:14
查看原帖
关于最长上升子序列优化写法的疑问
725807
lizeyuannb楼主2022/8/3 17:32

就是那个用 DilworthDilworth 定理优化到 O(n logn)O(n \ \mathrm{log}n) 的算法


for(int i = 2; i <= n; i ++) {
	if(f[len] < a[i])
		f[++len] = a[i];
   else
		*lower_bound(f+1, f+1+len, a[i]) = a[i];
}

求的是 lenlen,然而从代码来看, lenlen 的变化只和 f[len]f[len] 有关,那为什么下面的 else 还要修改 f[len]f[len] 以前的数值呢

2022/8/3 17:32
加载中...