你这个是O(n2)的做法啊，第二个要nlog(n)的做法才能过。
by mooktian @ 2024-04-27 15:56:43
用线性DP来做
by csZJY @ 2024-04-27 16:06:45
@[lucy2012](/user/1252442)
```cpp
#include<bits/stdc++.h>
using namespace std;
int /*sum1,sum2,dp1[10010],dp2[10010],*/a[100010];
int qdown[100010],qup[100010];//两个队列，qdown单调不递增，qup单调递增序列
int lendown,lenup;//队列的长度
int main(){
int n=1;
while(cin>>a[n]){
//dp1[n]=1;
//dp2[n]=1;
n++;
}
n--;
/*for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
if(a[j]>=a[i])
dp1[i]=max(dp1[i],dp1[j]+1);
if(a[j]<a[i])
dp2[i]=max(dp2[i],dp2[j]+1);
}
}
for(int i=1;i<=n;i++){
sum1=max(dp1[i],sum1);
sum2=max(dp2[i],sum2);
}*/
qdown[lendown++] = a[1];//维护一个单调不递增序列
for(int i = 2;i <= n;i++) {
int pos = upper_bound(qdown,qdown+lendown,a[i],greater<int>()) - qdown;//注意这里是单调不递增
qdown[pos] = a[i];//pos的位置更新成a[i]
if(pos == lendown) lendown++;//如果a[i]接在队尾则长度加1
}
qup[lenup++] = a[1];//维护一个单调递增序列
for(int i = 2;i <= n;i++) {
int pos = lower_bound(qup,qup+lenup,a[i]) - qup;//注意这个是单调递增
qup[pos] = a[i];//pos的位置更新成a[i]
if(pos == lenup) lenup++;//如果a[i]接在队尾则长度加1
}
//cout<<sum1<<endl<<sum2;//最好不要用endl，每次都要刷新缓存区，速度太慢
cout << lendown <<"\n" <<lenup;
return 0;
}
```
by mooktian @ 2024-04-27 16:30:39
@[lucy2012](/user/1252442) 帮你改了一下，不过差不多也是相当于重写了一遍。
by mooktian @ 2024-04-27 16:31:13