Readme

1964.Find-the-Longest-Valid-Obstacle-Course-at-Each-Position

本题的本质其实就是求最长（非严格）递增子序列。类似于LC.300，我们有NlogN的贪心解法。算法的核心是用数组来维护一个递增的数组arr。如果新元素x比数组的最后一个元素还大，那么显然以x结尾的LIS就是arr.size()+1.

如果新元素x不能添加在最后怎么办，我们找到arr里面第一个大于x的位置i，把arr[i]替换为x。显然以x结尾的LIS的长度就是i。那么问题来了，我们为什么要做“替换”呢？首先，替换之后arr依然是递增的序列。其次，这个arr整体“变矮”了，无论之后的新元素x是什么，对于它而言都更容易构造更长的LIS。