AcWing 3549. 最长非递减子序列 （lis或者状态机）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,a[N],pre[N],ne[N],f[2],ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]--;
    }
    for(int i=1;i<=n;i++){
        if(!a[i])pre[i]=++f[0];
        else pre[i]=f[1]=max(f[0],f[1])+1;
    }
    f[0]=f[1]=0;
    for(int i=n;i;i--){
        if(a[i])ne[i]=++f[1];
        else ne[i]=f[0]=max(f[1],f[0])+1;
    }
    for(int i=1;i<n;i++){
        ans=max(ans,pre[i]+ne[i+1]);
    }
    cout<<ans<<endl;
}