需要抽象一下，第一问就可以抽象为最长不上升子序列，第二问可以抽象为最长上升子序列长度。
就如下图的情况：
然后可以先 \(n^2\) 做法做，因为 \(n\ge 100000\) 所以要滚动数组，求最长不上升子序列可以反向从 n 开始递推。
我是 n^2 我不好
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
int n;
int a[N];
int f[N];
int ans1,ans2;
int main(){
while(cin>>a[++n]);
n-=1;
for(int i=n;i>=1;i--){
f[i]=1;
for(int j=n;j>i;j--){
if(a[i]>=a[j]){
f[i]=max(f[i],f[j]+1);
}
}
ans1=max(ans1,f[i]);
}
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<i;j++){
if(a[i]>a[j]){
f[i]=max(f[i],f[j]+1);
}
}
ans2=max(ans2,f[i]);
}
cout<<ans1<<"\n"<<ans2;
return 0;
}