$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

结论： $第一问求最长下降子序列，第二问求最长上升子序列$

思路：

1. 如果现有子序列的结尾数都小于当前数，那就创建一个新的序列
2. 否则，就将当前数放在现有子序列的大于等于当前数的最小结尾数的后面
3. 因此我们可以巧妙地发现，他们的结尾数呈一个最长上升子序列的形态

Example：

1. 母序列：389 207 155 300 299 170 158 65
2. 子序列1：389 207 155 65
3. 子序列2：300 299 170 158

可参考： 最长上升子序列 II

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int n;
int a[N];
int f[N],g[N];
int q[N];

int main()
{
    while(cin>>a[n]) n++;

    int res=0,cnt=0;
    for(int i=0;i<n;i++) 
    {
        f[i]=1,g[i]=1;
        for(int j=0;j<i;j++)
            if(a[j]>=a[i]) f[i]=max(f[i],f[j]+1); //下降
            else g[i]=max(g[i],g[j]+1); //上升

        res=max(res,f[i]);
        cnt=max(cnt,g[i]);
    }

    // 求最长上升子序列的 O(nlogn) 的写法
    // int cnt=0;
    // for(int i=0;i<n;i++)
    // {
    //     int l=0,r=cnt;
    //     while(l<r)
    //     {
    //         int mid=l+r+1>>1;
    //         if(q[mid]<a[i]) l=mid;
    //         else r=mid-1;
    //     }

    //     cnt=max(cnt,r+1);
    //     q[r+1]=a[i];
    // }

    cout<<res<<'\n'<<cnt<<endl;

    return 0;
}