本文共 690 字，大约阅读时间需要 2 分钟。

#include
   
    using namespace std;int a[100007];int cnt;int dp1[100007],dp2[100007];int main(){
       while(cin>>a[++cnt]);    cnt--;    dp1[1]=a[1];    dp2[1]=a[1];    int len1=1,len2=1;    for(int i=2;i<=cnt;i++)    {
           if(a[i]<=dp1[len1]) dp1[++len1]=a[i];        else        {
               int p1=upper_bound(dp1+1,dp1+len1+1,a[i],greater
    
     ())-dp1;//查找第一个大于a[i]的位置            dp1[p1]=a[i];        }        if(a[i]>dp2[len2]) dp2[++len2]=a[i];        else        {
               int p2=lower_bound(dp2+1,dp2+len2+1,a[i])-dp2;//查找第一个大于等于a[i]的位置            dp2[p2]=a[i];        }    }    cout<
     
      <
      
       <
      
     
    
   

转载地址：http://psgwi.baihongyu.com/