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

可以使用二分查找和动态规划的思想，时间复杂度为 O(n logn)。

具体的做法是，维护一个数组 dp，dp[i] 表示长度为 i 的最长上升子序列的末尾元素的最小值。初始时，dp[1] = a[1]，其余为 INF。然后从 i = 2 到 n，对于每个 a[i]，在 dp 数组中查找第一个大于等于 a[i] 的元素 dp[j]，将其替换为 a[i]。如果不存在这样的元素，说明 a[i] 大于所有的 dp[j]，此时应该将 dp 数组的长度加 1，即 dp[len+1] = a[i]，其中 len 表示当前 dp 数组的最大下标。最终，dp 数组的长度就是最长上升子序列的长度。

代码如下：

const int INF = 0x3f3f3f3f;
int dp[N], len = 1; // dp 数组和最大下标 len
dp[1] = a[1];
for (int i = 2; i <= n; ++i) {
    if (a[i] > dp[len]) { // 情况 1
        dp[++len] = a[i];
    } else { // 情况 2
        int pos = lower_bound(dp + 1, dp + len + 1, a[i]) - dp;
        dp[pos] = a[i];
    }
}

其中 lower_bound 函数可以使用 STL 中的 lower_bound，也可以手写实现。