最长递增子序列
Longest Increasing Subsequence
题目详情
问题：最长递增子序列
考察：数组、动态规划、二分查找
来源：Citadel
链接：https://www.jointaro.com/interviews/questions/longest-increasing-subsequence/
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3] Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7] Output: 1
Constraints:
1 <= nums.length <= 2500-104 <= nums[i] <= 104
Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
解析
思路：维护 tails 数组，tails[len] 表示长度为 len+1 的递增子序列的最小结尾。每个数用二分替换第一个不小于它的位置。
复杂度：时间 O(n log n)，空间 O(n)。