1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int y[100];

 4 int zs[100],zbx[100],zx[100],zbs[100];

 5 //zs 最长上升子序列 zbx最长不下降子序列 zx 最长下降子序列 zbs 最长不上升子序列

 6 bool cmp(int a,int b)

 7 {

 8     return a>b;

 9 }//不知道能不能用，尽管测试过没问题，但感觉还是不严谨，不推荐使用

10 int main()

11 {

12     int n;

13     scanf("%d",&n);

14     for(int i=1;i<=n;++i)

15     {

16         scanf("%d",&y[i]);

17     }

18     zs[1]=zbx[1]=zx[1]=zbs[1]=y[1];

19     int cnt=1;

20     for(int i=2;i<=n;++i)

21     {

22         if(y[i]>zs[cnt])

23         {

24             zs[++cnt]=y[i];

25         }

26         else

27         {

28             int p=lower_bound(zs+1,zs+cnt+1,y[i])-zs;

29             zs[p]=y[i];

30         }

31     }

32     printf("%d\n",cnt);//最长上升子序列长度

33     cnt=1;

34     for(int i=2;i<=n;++i)

35     {

36         if(y[i]>=zbx[cnt])

37         {

38             zbx[++cnt]=y[i];

39         }

40         else

41         {

42             int p=upper_bound(zbx+1,zbx+cnt+1,y[i])-zbx;

43             zbx[p]=y[i];

44         }

45     }

46     printf("%d\n",cnt);//最长不下降子序列长度

47     cnt=1;

48     for(int i=2;i<=n;++i)

49     {

50         if(y[i]<zx[cnt])

51         {

52             zx[++cnt]=y[i];

53         }

54         else

55         {

56             int  p=lower_bound(zx+1,zx+cnt+1,y[i],greater<int>() )-zx;

57             //int p=lower_bound(zx+1,zx+cnt+1,y[i],cmp )-zx;

58             zx[p]=y[i];

59         }

60     }

61     printf("%d\n",cnt);//最长下降子序列长度

62     cnt=1;

63     for(int i=2;i<=n;++i)

64     {

65         if(y[i]<=zbs[cnt])

66         {

67             zbs[++cnt]=y[i];

68         }

69         else

70         {

71             int  p=upper_bound(zbs+1,zbs+cnt+1,y[i],greater<int>() )-zbs;

72             //int p=upper_bound(zbs+1,zbs+cnt+1,y[i],cmp )-zbs;

73             zbs[p]=y[i];

74         }

75     }

76     printf("%d\n",cnt);//最长不上升子序列长度

77     return 0;

78 }