最长递增子序列（Longest Increasing Subsequence）

"这篇文章主要介绍了什么是最长递增子序列，并提供了两种不同的算法实现：动态规划和二分查找优化的动态规划。" 最长递增子序列（Longest Increasing Subsequence，LIS）是序列中一个特殊的子序列，它满足子序列中的元素严格递增，且长度尽可能长。例如，在序列 L=<a1, a2, ..., an> 中，如果存在子序列 Lin=<aK1, ak2, ..., akm>，满足 k1 < k2 < ... < km 且 aK1 < ak2 < ... < akm，那么 Lin 就是一个递增子序列。目标是找到这样的子序列，使得 m 的值最大。 解决这个问题，可以采用以下两种方法： 1. 动态规划（Dynamic Programming，DP）方法： 动态规划是一种将大问题分解为小问题来求解的方法。对于LIS问题，我们可以创建一个数组 b[n]，其中 b[i] 表示以 a[i] 结尾的最长递增子序列的长度。初始化 b[0] = 1，然后对于每个 i (1 <= i < n)，遍历所有小于 i 的 j (0 <= j < i)，如果 a[i] > a[j] 且 b[j] + 1 > b[i]，则更新 b[i] = b[j] + 1。最后，数组 b 中的最大值即为最长递增子序列的长度。这种方法的时间复杂度为 O(n^2)。 示例代码： ```cpp int getMaxLen(int* sel, int N) { int n1 = 1, n2 = 1, i1 = 0, i2 = 0; for (int i = 1; i < N; i++) { if (sel[i] > sel[i - 1]) { n2++; if (n2 > n1) n1 = n2; } else n2 = 1; } return n1; } ``` 2. 二分查找优化的动态规划（Binary Search Enhanced Dynamic Programming）： 这种方法利用了二分查找来优化动态规划的过程。在每次更新 b[i] 时，我们可以使用二分查找来找到合适的位置，这样可以减少比较次数，从而降低时间复杂度到 O(n log n)。首先计算出所有以 a[i] 结尾的子序列长度，然后在更新 b[i] 时，通过二分查找找到 b[j] 的位置，使得 a[j] < a[i]，并更新 b[i] = max(b[j] + 1, b[i])。 示例代码： ```cpp int find(int* a, int len, int n) { int left = 0, right = len, mid = (left + right) / 2; while (left < right) { // ... } } int main() { // ... for (int i = 1; i < n; i++) { b[i] = 1; int index = find(a, i, a[i]); if (index != 0 && a[index - 1] < a[i]) { b[i] = b[index - 1] + 1; } } // ... } ``` 这两种方法各有优缺点，动态规划方法简单直观，但时间复杂度较高；而二分查找优化的动态规划方法虽然实现稍微复杂，但效率更高。在实际应用中，根据具体需求和数据规模可以选择合适的方法。