题意翻译
给定一长度为n的数列,请在不改变原数列顺序的前提下,从中随机的取出一定数量的整数,并使这些整数构成单调上升序列。 输出这类单调上升序列的最大长度。
数据范围:1<=n<=1000001<=n<=1000001<=n<=100000
和On^2算法不同,dp数组存储的不再是子序列长度了,而是一个最小的递增子序列。用len这个变量存储最小子序列的长度(或者说末尾位置),当a[i]>dp[len]时直接把a[i]添加到子序列的末尾,当a[i]<=dp[len]时,用lower_bound函数找到在子序列中第一个比a[i]大的数的位置,贪心地把这个数用a[i]替换掉即可。
#include <bits/stdc++.h>
using namespace std;
int n;
int a[];
int dp[];
int main()
{
cin>>n;
int i;
for(i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
int len=;
for(i=;i<=n;i++)
{
if(i==)
{
dp[]=a[];
len++;
continue;
}
else
{
if(a[i]>dp[len])
{
dp[++len]=a[i];
continue;
}
else
{
int pos=lower_bound(dp+,dp+len+,a[i])-dp;
dp[pos]=a[i];
}
}
}
cout<<len;}