最长上升子序列 II 题解
题目传送门：AcWing 896. 最长上升子序列 II
一、题目描述
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式：
- 第一行包含整数 N
- 第二行包含 N 个整数，表示完整序列
输出格式：
- 输出一个整数，表示最大长度
数据范围：
- 1 ≤ N ≤ 100000
- -10⁹ ≤ 数列中的数 ≤ 10⁹
二、题目分析
这道题要求我们找到一个序列中最长的严格递增子序列的长度。与普通的最长上升子序列问题不同，本题的数据范围较大（N ≤ 1e5），因此需要使用优化的算法。
三、解题思路
传统的动态规划解法时间复杂度为O(n²)，对于n=1e5的情况会超时。我们需要使用贪心+二分的方法将时间复杂度优化到O(nlogn)。
基本思路是维护一个数组a，其中a[i]表示长度为i+1的上升子序列的最小末尾元素。对于每个元素，我们使用二分查找来确定它应该插入的位置，从而保持数组a的单调性。
四、算法讲解
算法原理
- 贪心思想：我们希望上升子序列尽可能长，因此需要让序列上升得尽可能慢，即每次在上升子序列最后加上的数尽可能小。
- 单调性：数组a是一个严格递增的数组，这保证了我们可以使用二分查找。
- 二分查找：对于每个新元素，如果它大于数组a的最后一个元素，则直接添加到末尾；否则，使用二分查找找到第一个大于等于它的位置并替换。
算法实现步骤
- 初始化空数组a和计数器cnt=0
- 遍历输入序列中的每个元素x：
- 如果x大于a的最后一个元素，直接添加到a末尾，cnt加1
- 否则，使用二分查找找到a中第一个大于等于x的位置，并用x替换该位置的值
- 最终cnt即为最长上升子序列的长度
例子讲解
以输入样例为例：
7
3 1 2 1 8 5 6
处理过程：
- 3 → [3], cnt=1
- 1 → [1], cnt=1 (替换3)
- 2 → [1,2], cnt=2
- 1 → [1,2], cnt=2 (1替换1，无变化)
- 8 → [1,2,8], cnt=3
- 5 → [1,2,5], cnt=3 (替换8)
- 6 → [1,2,5,6], cnt=4
最终结果为4。
五、代码实现
#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int N = 1e5 + 10;
int n;
int a[N];
int cnt = 0, f[N];// STL大法
void solve1()
{cin >> n;for (int i = 1; i <= n; i ++){int x;cin >> x;if (cnt == 0 || a[cnt - 1] < x)a[cnt++] = x;else*lower_bound(a, a + cnt, x) = x; // 使用STL的lower_bound找到第一个≥x的位置并替换}cout << cnt;
}// 手写二分
void solve2()
{cin >> n;for (int i = 1; i <= n; i ++){int x;cin >> x;if (cnt == 0 || a[cnt - 1] < x)a[cnt++] = x;else{int l = -1, r = cnt + 1;while (l + 1 != r) // 二分查找第一个≥x的位置{int mid = l + r >> 1;if (a[mid] < x)l = mid;else r = mid;}a[r] = x; // 替换该位置的值}}cout << cnt;
}signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);// solve1();solve2();return 0;
}
六、重点细节
- 初始化边界：二分查找时，左边界设为-1，右边界设为cnt+1，这样可以处理所有可能的情况
- 严格递增：题目要求严格递增，因此比较时使用<而不是≤
- 替换策略：当找到第一个≥x的位置时，直接替换可以保证后续更长的子序列更容易形成
- 数组维护：数组a的长度cnt即为当前找到的最长上升子序列长度
七、复杂度分析
- 时间复杂度：O(nlogn)，每个元素需要进行一次二分查找，二分查找的时间复杂度为O(logn)
- 空间复杂度：O(n)，需要额外的数组a来存储中间结果
八、总结
本题通过贪心+二分的方法，将最长上升子序列问题的时间复杂度从O(n²)优化到O(nlogn)，能够高效处理大规模数据。关键在于维护一个单调递增的数组，并通过二分查找来快速确定每个元素的插入位置。