1. 朴素解法，复杂度On2，只能过一半的点。

#include
    
     using namespace std;typedef struct{    int num;    int len;    int dlen;}Missile;Missile miss[100010];int cnt=0,n=1,maxnum=0,maxl=0;int main(){    while(cin>>miss[n].num){        n++;    }    n--;    for(int i=n;i>=1;i--)    {        for(int j=i;j<=n;j++)        {//dp            if(miss[i].num>=miss[j].num)            {                miss[i].len=max(miss[i].len,miss[j].len+1);            }            if(miss[i].num
    

1. 分析题意可知求一个最长不升子序列，和一个最长上升子序列，转换为LIS线性dp求解，复杂度为Onlogn

#include
    
     using namespace std;int arr[100010],le[100010],gt[100010];int p1,p2;int main(){    int n=1;    while(cin>>arr[n])n++;    n--;    le[1]=gt[1]=arr[1];    p1=p2=1;    for(int i=2;i<=n;i++)    {        if(arr[i]<=le[p1])le[++p1]=arr[i];//下降不升子序列，求最多打下数目            //10 8 6 +7 需要替换6 +8替换6            else le[upper_bound(le+1,le+p1+1,arr[i],greater
     
      ())-le]=arr[i];        if(arr[i]>gt[p2])gt[++p2]=arr[i];//上升子序列，求系统数目            //1 3 5 7 +5 替换5 +6替换7            else gt[lower_bound(gt+1,gt+p2+1,arr[i])-gt]=arr[i];    }    cout<
      
       <
       
        <