题意概括

给定一个长度为 $N$ 的数字序列 $A = \{a_1, a_2, \dots, a_N\}$，找到其一个子序列 $B = \{b_1, b_2, \dots, b_k\}$，使得该子序列是严格单调递增的（即 $b_1 < b_2 < \dots < b_k$），并且其长度 $k$ 是所有可能的递增子序列中最长的。输出这个最长的长度。

数据范围:

• 序列长度 $N$ 满足 $1 \le N \le 10^5$。
• 序列中的每个元素 $a_i$ 满足 $-10^9 \le a_i \le 10^9$。

基础知识

最长递增子序列 (Longest Increasing Subsequence, LIS)

解决 LIS 问题通常有两种方法：动态规划和贪心 + 二分查找。

1. 动态规划 (DP) - $O(N^2)$

   • 定义状态：$dp[i]$ 表示以第 $i$ 个元素 $a_i$ 结尾的最长递增子序列的长度。
   • 状态转移方程：$dp[i] = \max_{0 \le j < i, a_j < a_i} \{dp[j]\} + 1$。
   • 遍历所有 $j < i$，如果 $a_j < a_i$，说明 $a_i$ 可以接在以 $a_j$ 结尾的递增子序列后面，形成一个更长的子序列。我们取所有这些可能情况中的最大长度加一。
   • 最终答案为 $\max_{0 \le i < N} \{dp[i]\}$。
   • 这种方法对于 $N=10^5$ 的数据范围会超时。

2. 贪心 + 二分查找 - $O(N \log N)$

   • 这是解决本题的标准高效算法。
   • 我们维护一个数组 d，其中 d[k] 存储的是所有长度为 $k+1$ 的递增子序列中，结尾元素的最小值。这个 d 数组一定是单调递增的。
   • 遍历原始序列 $A$ 的每一个元素 $x$：
     • 如果 $x$ 大于 d 数组中所有元素（即大于 d 的最后一个元素），说明 $x$ 可以接在目前最长的递增子序列后面，形成一个更长的递增子序列。我们将 $x$ 直接添加到 d 数组的末尾，LIS 的长度加一。
     • 如果 $x$ 不大于 d 的最后一个元素，我们就在 d 数组中找到第一个大于或等于 $x$ 的元素 d[k]，并用 $x$ 替换它。这表示我们找到了一个长度为 $k+1$ 的、但结尾更小（为 $x$）的递增子序列。这个更小的结尾元素为后续元素提供了更大的增长潜力。
   • 由于 d 数组是单调的，查找过程可以用二分查找来完成，时间复杂度为 $O(\log N)$。
   • 遍历完整个序列 $A$ 后，d 数组的长度就是原序列 LIS 的长度。

C++ 代码实现

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 5;

int n;
int a[N];
vector<int> d; // d[k] 存储长度为 k+1 的 LIS 的最小结尾元素

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    d.push_back(a[0]); // 初始化，LIS 长度为 1

    for (int i = 1; i < n; i++) {
        int x = a[i];
        if (x > d.back()) {
            // 如果 x 比所有已知 LIS 的结尾都大，它可以扩展最长的 LIS
            d.push_back(x);
        } else {
            // 否则，找到第一个大于等于 x 的位置，用 x 替换它
            // 这会得到一个结尾更小的同样长度的 LIS，更有潜力
            auto it = lower_bound(d.begin(), d.end(), x);
            *it = x;
        }
    }

    cout << d.size() << endl;

    return 0;
}