最长上升子序列

O(n^2)

f[i]=max{f[j]+1}, a[j]<=a[i]

O(nlogn)

将思维过程转换一下。 假设i前面存在的上升子序列长度为1~len 那么只要将a[i]接到某个比它小的数a[j]后面，就构成了一个新的子序列，且f[i]=f[j]+1 想要f[i]尽量大，要求f[j]尽量大 一种策略是从len开始往前找，对于某个len，可能有j1,j2,…jm都满足f[jx]=len 那么只要其中有一个jx，使得a[jx]<=a[i]，就可以将i接到它后面 很明显，最有可能的jx是min{jn} 所以有了如下结论

f[i]=max{len} | min{jn}<=i

所以只要维护数组minj[len]，记录满足f[j]=len的最小的j。 容易知道minj是单调不降的，所以可以二分查找。 具体做法就是二分查找minj，找到最大的len满足minj[len]<=a[i] f[i]=len+1 最后用a[i]更新一下minj：minj[f[i]]=max(minj[f[i]],a[i])