NC26156. G. 最长递增长度
描述
输入描述
第一行，一个整数n (2<=n<=50000)，表示序列的长度
第二行，有n个整数 (-10^9 <= S[i] <= 10^9)，表示这个序列
输出描述
输出一个整数，表示最长递增子序列的长度
示例1
输入:
6 4 0 5 8 7 8
输出:
4
C++14(g++5.4) 解法, 执行用时: 22ms, 内存消耗: 396K, 提交时间: 2020-08-19 18:56:19
#include<bits/stdc++.h>
using namespace std;
int t,n,s[50001],a;
int main()
{
s[0]=0;
cin>>n;
while(n--)
{
cin>>a;
if(a>s[t])
s[++t]=a;
else
*lower_bound(s+1,s+t+1,a)=a;
}
printf("%d\n",t);
}
C++11(clang++ 3.9) 解法, 执行用时: 39ms, 内存消耗: 448K, 提交时间: 2019-06-03 15:53:04
#include<bits/stdc++.h>
using namespace std;
int t,n,s[50001],a;
int main()
{s[0]=0;
cin>>n;
while(n--)
{cin>>a;
if(a>s[t])
s[++t]=a;
else
*lower_bound(s+1,s+t+1,a)=a;}
printf("%d\n",t);}