hahaha1215 @ 2024-11-10 10:53:18
可以试试这个例子:
5
1 2 3 2 3
原因在于,给定的数组中可能有重复的元素。
当定义f[i]为长度为i的递增子序列的最小结尾元素时
考虑在上面的例子中枚举到a[4],此时f[1]=1,f[2]=2,f[3]=3,如果每次找到第一个大于当前a[1]的f值去更新,那么就会更新f[3]=2,而这样是错误的,原因是f[2]=2,不将a[4]=2连在f[2]=2后面,这样降不满足严格递增。
我们改成去更新第一个大于等于当前a[i]的f值即可AC。
by hahaha1215 @ 2024-11-10 10:56:56
本质上,我们是想找到最后一个小于a[i]的f[j],并且更新f[j+1]
所以改成先找到最后一个小于a[i]的f[j],再更新f[j+1]也是正确的
by Sakura_Love @ 2024-12-05 16:57:43
好!