题目描述

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式
第一行包含整数 N。

第二行包含 N 个整数，表示完整序列。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N≤100000，
−10⁹≤数列中的数≤10⁹

输入样例

7
3 1 2 1 8 5 6

输出样例

4

思路

在AcWing的题解区再现妙手，原题解链接为在此。
大体的思路是这样的，使用vector模拟堆栈，这个堆栈的长度维护的便是最长上升子序列的长度。首先将序列的第一个数存入栈，从第二个数开始遍历序列。

• 如果第i个数大于栈顶元素，那么这个数也需要入栈（显然，入栈的元素大于之前的栈顶元素，栈内保持升序）。这个数入栈之后，使栈的规模提升了，即提高了最长上升子序列的规模，对答案产生了直接贡献；
• 否则（即，第i个数小于等于栈顶元素），使用lower_bound函数（模拟的是二分，寻找的是目标可迭代对象中第一个大于等于目标值<此处的目标值便是这个第i个数>的数的位置指针，加*可以解除指针使其退化为引用）在堆栈中找到第一个大于等于第i个数的数，将堆栈中的这个数替换为第i个数。值得注意的是，替换的数可能在当前的栈顶，也可能在堆栈中间的某个位置，如果在堆栈中间的某个位置的话（甚至可能是栈底，即v[0]），由于最后的答案是v.size()，因此它没有直接改变答案，但是它有改变答案的潜力，如序列2 3 4 1 2 3 4，遍历到i = 4时，1便替代了栈底的2，遍历到i = 6时，答案仍不变，而到i = 7时，a[i = 7] ＞ v.back()需要进栈，栈的规模扩大了，答案才更新。

代码实现

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn] = {0};
vector<int> v;
int n;
int main()
{ios::sync_with_stdio(false);cin.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}v.push_back(a[1]);for(int i=2;i<=n;i++){if(a[i] > v.back()){v.push_back(a[i]);}else{*lower_bound(v.begin(), v.end(), a[i]) = a[i];}}cout<<v.size();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！