300. 最长递增子序列 - 力扣（LeetCode）

维护一个数组tail，其中，元素tail[k] 表示 长度为k的上升子序列的末尾元素的最小值。

数组tail是严格递增的

对任意下标 i < j，tail[i] < “tail[j]所在的序列 的 长度为m的前缀的结尾元素” <= tail[j]。
第一个 “<” 是因为 长度为n的上升子序列的长度为m的前缀 都是 长度为m的上升子序列。
第二个 “<=” 是因为 tail[j]所在的序列 是上升的。

更新lower_bound(tail,nums[n])

已知 nums[0…n-1]的tail 和 nums[n]，
把 nums[n] 追加到 末尾元素小于nums[n]的上升子序列 的后面，将产生一组新的上升子序列。
在新的上升子序列中，只有最长的那些可能更新 数组tail，
或者说，在新的上升子序列中，非最长那些不可能更新 数组tail，
即，“非最长的序列(设长度为s)的末尾元素nums[n]” > “最长的新序列的长度为s的前缀的结尾元素” >= tail[s]。

代码

	int lengthOfLIS(std::vector<int> nums) {
		std::vector<int> tail(nums.size(), INT_MAX);
		for (int num:nums) *std::lower_bound(tail.begin(), tail.end(), nums[i]) = nums[i];
		return std::lower_bound(tail.begin(), tail.end(), INT_MAX) - tail.begin();
	}