c++ 求最长子序列n*logn的复杂度
时间: 2024-05-02 22:17:01 浏览: 10
最长子序列问题可以使用动态规划来解决,其时间复杂度为 $O(n^2)$。但是,我们可以使用二分查找来优化算法,使其时间复杂度降为 $O(n\log n)$。
具体来说,我们可以维护一个数组 $d$,其中 $d[i]$ 表示长度为 $i$ 的子序列的末尾元素的最小值。对于每个元素 $a_i$,我们可以在数组 $d$ 中查找第一个大于等于 $a_i$ 的元素 $d[j]$,然后更新 $d[j]=a_i$。如果 $a_i$ 大于数组 $d$ 的所有元素,则将 $a_i$ 加入数组 $d$ 的末尾。
最后,最长子序列的长度就是数组 $d$ 的长度。
下面是 C++ 代码实现:
```c++
int LIS(vector<int>& nums) {
vector<int> d;
for (int i = 0; i < nums.size(); i++) {
auto it = lower_bound(d.begin(), d.end(), nums[i]);
if (it == d.end()) {
d.push_back(nums[i]);
} else {
*it = nums[i];
}
}
return d.size();
}
```
其中 `lower_bound(d.begin(), d.end(), nums[i])` 函数用于在数组 `d` 中查找第一个大于等于 `nums[i]` 的元素。这个函数的时间复杂度为 $O(\log n)$。因此,整个算法的时间复杂度为 $O(n\log n)$。