最长上升子序列（二分）

题目描述

给定一个长度为$nn$的数组$a_1,a_2,\dots ,a_{n}a\_1,a\_2,\dots ,a\_n$，问其中的最长上升子序列的长度。

所有数据保证$1\le n\le 100000,1\le a_i\le 10^{9}1\le n\le 100000,1\le a\_i\le 10^9$。

分析

$c[i]c[i]$：表示上升子序列为$ii$的最后一个元素的最小值

如果，那么$c[++len]=a[i]c[++len]=a[i]$

否则，从$0-len0-len$进行二分，将$a[i]a[i]$存入

$lenlen$为当前最长上升子序列

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,len,a[maxn],c[maxn];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		if(a[i]>c[len])
			c[++len]=a[i];
		else{
			int l=0,r=len;
			while(l+1<r){
				int mid=(l+r)/2;
				if(c[mid]<a[i])
					l=mid;
				else
					r=mid;
			}
			c[r]=a[i];
		}
	}
	printf("%d",len);
}