[codevs 3995] 최장 엄격 상승 서브 서열(강화판)
2785 단어 ====동적 기획 =====서열형
#include
#include
#include
#include
using namespace std;
const int MAXN = 1000000 + 5;
int g[MAXN],len,n,a[MAXN];
int find(int x)
{
int l = 0,r = n;
int mid = (l + r) / 2;
while(l <= r)
{
if(g[mid] < x)
l = mid + 1;
else if(g[mid] > x)
r = mid - 1;
else
return mid;
mid = (l + r) / 2;
}
return l;
}
void dpdpd()
{
len = 1;
memset(g,0x3f,sizeof(g));
g[0] = -1;
g[1] = a[1];
for(int i = 2;i <= n;i ++)
{
int j = find(a[i]);
g[j] = min(g[j],a[i]);
len = max(len,j);
}
return;
}
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i ++)
scanf("%d",&a[i]);
dpdpd();
printf("%d
",len);
return 0;
}