$\Huge Solution$

---

---

---

题目描述

给定一个长度为 $N$ 的整数序列 $a_1, a_2, \dots, a_N$，求该序列中最长严格递增子序列的长度。

子序列是指从原序列中删除若干个元素（也可以不删除）后，剩余元素保持原有相对顺序组成的序列。
严格递增是指子序列中的元素满足 $b_1 < b_2 < \dots < b_k$。

输入格式

• 第一行包含一个整数 $N$，表示序列的长度。
• 第二行包含 $N$ 个整数，表示序列 $a$。

输出格式

• 输出一个整数，表示最长严格递增子序列的长度。

数据范围

• $1 \le N \le 1000$ (针对 $O(N)$ 解法)
• 若 $N$ 更大（如 $10$），需使用 $O(N \log N)$ 解法。

---

解题思路

本题是经典的动态规划问题。我们提供两种解法：动态规划 ($O(N)$) 和 贪心 + 二分查找 ($O(N \log N)$)。

方法一：动态规划 ($O(N)$)

1. 状态定义
   设 dp[i] 表示以第 $i$ 个元素 $a[i]$ 结尾的最长严格递增子序列的长度。

2. 状态转移方程
   对于每个位置 $i$，我们需要检查它之前的所有位置 $j$ ($0 \le j < i$)：

• 如果 $a[j] < a[i]$，说明 $a[i]$ 可以接在以 $a[j]$ 结尾的递增子序列后面，形成一个新的更长的递增子序列。
• 此时，dp[i] 可以更新为 dp[j] + 1。
• 为了得到最长的长度，我们需要取所有满足条件的 $j$ 中的最大值。

即：

$$dp[i] = \max_{0 \le j < i, a[j] < a[i]} (dp[j] + 1)$$

如果没有任何 $j$ 满足 $a[j] < a[i]$，则 dp[i] 保持初始值 1（即只包含 $a[i]$ 自身）。

3. 初始化

• 所有 dp[i] 初始化为 1，因为每个元素本身至少构成一个长度为 1 的子序列。

4. 最终答案

• LIS 不一定以最后一个元素结尾，因此答案是 dp 数组中的最大值，即 $\max(dp[0], dp[1], \dots, dp[N-1])$。

5. 代码实现 (C++)

include <iostream>
include <algorithm>

using namespace std;

const int MAXN = 1005;
int n;
int a[MAXN];
int dp[MAXN];

int main() {
    // 优化 IO
    ios::sync_with_stdio(false);
    cin.tie(NULL);

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

    // 初始化 dp 数组
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
    }

    // 动态规划过程
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    // 寻找最大值
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dp[i]);
    }

    cout << ans << endl;

    return 0;
}

6. 复杂度分析

• 时间复杂度：$O(N)$，因为有两层嵌套循环。
• 空间复杂度：$O(N)$，用于存储 a 和 dp 数组。

---

方法二：贪心 + 二分查找 ($O(N \log N)$)

当 $N$ 较大（如 $10$ 或更大）时，$O(N)$ 会超时，需要使用更高效的算法。

1. 核心思想
   维护一个数组 tails，其中 tails[k] 存储长度为 $k+1$ 的递增子序列的最小末尾元素。

• 我们希望子序列的末尾元素尽可能小，这样后续才有更多机会接上更大的数，从而形成更长的子序列。
• tails 数组本身是严格递增的。

2. 算法流程
   遍历数组中的每个元素 $x$：

3. 如果 $x$ 大于 tails 的最后一个元素，说明 $x$ 可以延长当前最长的子序列，将 $x$ 追加到 tails 末尾。

4. 否则，在 tails 中找到第一个大于或等于 $x$ 的元素，并用 $x$ 替换它。这一步保证了对于相同长度的子序列，我们保留了更小的末尾元素。

   • 这里可以使用 lower_bound 进行二分查找。

5. 最终答案

• tails 数组的长度即为最长递增子序列的长度。

4. 代码实现 (C++)

include <iostream>
include <vector>
include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    vector<int> tails;
    
    for (int x : a) {
        // 在 tails 中查找第一个 >= x 的位置
        auto it = lower_bound(tails.begin(), tails.end(), x);
        
        if (it == tails.end()) {
            // x 比所有末尾都大，延长子序列
            tails.push_back(x);
        } else {
            // 替换该位置的值，使末尾更小
            *it = x;
        }
    }

    cout << tails.size() << endl;
    return 0;
}

5. 复杂度分析

• 时间复杂度：$O(N \log N)$，遍历 $N$ 个元素，每次二分查找耗时 $O(\log N)$。
• 空间复杂度：$O(N)$，最坏情况下 tails 长度为 $N$。

---

常见错误与注意事项

1. 非严格递增 vs 严格递增：

   • 题目要求严格递增 ($<$)，因此在 DP 中判断条件是 a[j] < a[i]，在二分查找中使用 lower_bound（找第一个 $\ge x$ 的位置并替换）。
   • 如果是非严格递增 ($\le$)，DP 条件改为 a[j] <= a[i]，二分查找使用 upper_bound（找第一个 $> x$ 的位置并替换）。

2. 答案不是 dp[n-1]：

   • 很多初学者误以为 LIS 必须以最后一个元素结尾，从而直接输出 dp[n-1]。这是错误的，必须遍历整个 dp 数组找最大值。

3. 初始化问题：

   • dp 数组必须初始化为 1，而不是 0。

4. 数据范围：

   • 如果 $N \le 5000$，$O(N)$ 解法通常可以通过。
   • 如果 $N > 5000$，建议使用 $O(N \log N)$ 解法。

总结

• 小规模数据：使用动态规划，思路清晰，易于实现。
• 大规模数据：使用贪心 + 二分查找，效率高，是面试和竞赛中的标准解法。

根据题目给出的数据范围选择合适的解法即可。