给定一个长度为N的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数N。
第二行包含N个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N≤100000,
−109≤数列中的数≤109
输入样例:
7
3 1 2 1 8 5 6
输出样例:
4
/*
状态表示:f[i]表示长度为 i 的上升子序列;
属性:长度为 i 的最长上升子序列的结尾的最小值;
状态计算: f[i+1]必大于等于f[i]所以可以二分找到当前数可更新的长度最长的上升序列,
使此序列的长度加一;
贪心证明: 贪心值必等于最大值
贪心所得值必小于等于最大值 (必然);
贪心值必大于等于最大值:贪心将每个值更新可更新的长度最长的上升序列
保证了每个长度的最长上升子序列的最大值最小,
而非贪心可能将长度小于当前数可更新的长度最长的的上升序列的末位数更新;
这就导致当下一个数插入时贪心可将最长上升子序列长度加一而非贪心不能;
所以贪心值必大于等于最大值;
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+520,inf=0x3f3f3f3f;
ll A[N],f[N];
int main()
{
ll n;
cin>>n;
for(ll i=1;i<=n;i++)cin>>A[i];
f[0]=-inf;ll len=0;
for(ll i=1;i<=n;i++)
{
ll l=0,r=len;
while(l<r)
{
ll mid=l+r+1>>1;
if(f[mid]<A[i])l=mid;
else r=mid-1;
}
len=max(len,r+1);
f[r+1]=min(f[r+1],A[i]);
}
cout<<len<<endl;
}