Longest Increasing Sub sequence "Length" O(nLog(n) )

LIS "Length"O(nLog(n) ).cpp

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
 
int a,num[120000],n,ans[120000],sz;
 
int main(){ 
	while (scanf("%d",&n) == 1){
		for(a=0;a<n;a++) scanf("%d",&num[a]);
		sz=0;
		for(a=0;a<n;a++) {
			int* it = lower_bound(ans,ans+sz,num[a]);
			if (it != ans+sz) *it=num[a];
			else ans[sz++]=num[a];
		}
		printf("%d\n",sz);
	}
	return 0;
}