Has Not Appeared. *

理解最长递增子序列（LIS）问题是一个经典的DP问题。在给定的数组中，目标是找到最长的严格递增的子序列。

子序列

子序列是通过删除一些或不删除元素，从原数组中得到的序列，且保留原顺序。例如，在数组 `[3, 10, 2, 1, 20]` 中，`[3, 10, 20]` 就是一个子序列。

例题：

问题概述

给定一个数组 `A`，找到其中最长的子序列，且子序列中的每个元素都比前一个元素大。这就是LIS问题。

朴素动态规划解决方案 (时间复杂度 O(N^2))

朴素方法使用动态规划（DP），时间复杂度为 O(N²)。该方法逻辑简单，但在处理较大数组时效率低。

朴素动态规划方法解释：

1. 创建一个 DP 数组 `dp[]`，其中每个元素 `dp[i]` 表示以索引 `i` 结尾的最长递增子序列的长度。

2. 对于每个元素 `A[i]`，遍历之前的所有元素 `A[j]`（`j < i`）。如果 `A[j] < A[i]`，则 `A[i]` 可以扩展以 `A[j]` 结尾的子序列。

3. 更新 `dp[i]`，使其为 `dp[i]` 和 `dp[j] + 1` 的较大值。

4. 最后的结果是 `dp[]` 数组中的最大值。

#include <vector>using namespace std;int find_lis(const vector<int>& a) {int lis = 0;vector<int> dp(a.size(), 1);for (int i = 0; i < a.size(); i++) {for (int j = 0; j < i; j++) {if (a[j] < a[i]) {dp[i] = max(dp[i], dp[j] + 1);}}lis = max(lis, dp[i]);}return lis;}

时间复杂度：O(N²)，因为对于每个元素，我们都要遍历之前的所有元素以计算最长子序列。

空间复杂度：O(N) 用于存储 DP 数组。

效率不高。

二分查找方法：

通过维护一个递增序列，并使用**二分查找**进行高效更新，优化后的方法将时间复杂度降低到 O(N log N)。

关键思路：

与其维护一个完整的 DP 数组，我们可以维护一个代表不同长度递增子序列的最小可能尾元素的列表。通过二分查找，我们可以在对数时间内高效地更新该列表。

1. 维护一个列表 `dp[]`，其中 `dp[i]` 保存长度为 `i+1` 的递增子序列的最小尾值。

2. 对于每个元素 `A[i]`，使用**二分查找**找到 `A[i]` 可以扩展子序列的位置。

3. 如果 `A[i]` 大于 `dp[]` 中的所有元素，将其添加到列表末尾。

4. 如果 `A[i]` 可以替换 `dp[]` 中的某个元素（通过二分查找找到），则替换该元素，以确保 `dp[]` 始终保持最小可能尾元素。

5. 最终，`dp[]` 数组的长度就是最长递增子序列的长度。

优化代码

#include <vector>#include <algorithm>using namespace std;int find_lis(const vector<int>& a) {vector<int> dp;for (int i : a) {// 使用二分查找找到要替换的位置int pos = lower_bound(dp.begin(), dp.end(), i) - dp.begin();if (pos == dp.size()) {dp.push_back(i);  // 可以扩展子序列} else {dp[pos] = i;  // 替换元素以保持最小可能值}}return dp.size();}

- **时间复杂度**：由于每个元素的二分查找，时间复杂度为 O(N log N)。

- **空间复杂度**：O(N) 用于存储 `dp[]` 列表。

常见的LIS应用

Non-intersecting Segments

一个相关问题是找到最大数量的不相交线段。这个问题可以简化为 LIS 问题，将线段视为区间，并确保没有两个区间重叠。

Minimum Number of Increasing Sequences

在另一个应用中，目标是将一个数组划分为最少数量的递增子序列。这个问题可以通过计算最长非递增子序列的长度来解决，并使用该长度来对数组进行划分。

Summary

问题是动态规划和算法中的基础问题，但是在金赛中还未出现过。尽管 O(N²) 的朴素解决方案适用于较小数组，但使用二分查找优化的 O(N log N) 方法对于处理大型数据集至关重要。理解这个问题不仅能增强算法技能，还能为解决各种与序列相关的问题铺平道路。