给定一个长度为 n 的序列 {an}，求其最长上升子序列长度。O(n logn)

可以使用二分查找和动态规划来解决这个问题，时间复杂度为 O(n logn)。

首先，我们定义一个数组 dp，其中 dp[i] 表示以第 i 个元素为结尾的最长上升子序列的长度。显然，dp[0] = 1。然后，我们从 i=1 开始遍历数组，对于每个 i，我们需要找到其中一个最大的 j，满足 a[j] < a[i] 且 dp[j] 是所有满足条件的 j 中最大的。然后，dp[i] 就等于 dp[j] + 1。

为了找到 j，我们可以使用二分查找来进行优化。具体来说，我们维护一个数组 b，其中 b[k] 表示长度为 k 的上升子序列中最后一个元素的最小值。我们从左到右遍历数组 a，对于每个 a[i]，我们在 b 中查找第一个大于等于 a[i] 的元素 b[j]，然后将 b[j] 更新为 a[i]。如果 b 中没有大于等于 a[i] 的元素，那么我们将 a[i] 加入到 b 的末尾。

最后，b 的长度就是最长上升子序列的长度。

以下是 Python 代码实现：

def lengthOfLIS(nums):
    n = len(nums)
    dp = [1] * n
    b = [float("inf")] * (n + 1)
    b[0] = float("-inf")

    for i in range(n):
        # 二分查找
        l, r = 0, i + 1
        while l < r:
            mid = (l + r) // 2
            if b[mid] < nums[i]:
                l = mid + 1
            else:
                r = mid
        # 更新 b[j]
        j = l
        b[j] = nums[i]
        # 更新 dp[i]
        dp[i] = j

    return max(dp)

时间复杂度为 O(n logn)。