保留一个向量“v[x] = y”，其中 y 是原始序列的最小元素，它给出了长度为 x 的最长递增子序列。原来你只有v[0] = -inf.
遍历一个元素的序列，使用二进制搜索a在向量中查找它。v你不会找到a确切的，而是最大x的v[x] <= a（<如果它严格增加）。因此，以 a 结尾的最长递增子序列将是 length x+1。现在更新v[x+1]为 a（它不能小于 a，否则您的搜索应该有 return x+1），您可能需要扩展向量。
LIS 的长度是向量的大小。如果您需要重建解决方案，请跟踪您使用的位置。