思路分析

1：结论：最长上升子序列的数目等于最少的下降子序列数目（本文皆指严格上升和下降），同理，最长下降子序列的数目等于最少的上升子序列的数目

2：如何求出最少的上升或者下降子序列的数目，我们就可以采用贪心的方法了

（1）：最少的上升子序列的数目：我们可以构造一个数组假设已经存下所有上升子序列的每一个末尾的值（比如 1 2 3，存的就是3），这时，当我们新遍历一个元素时，如果说当前元素值小于等于数组末尾值，那么这个元素就是一个单独的上升子序列，所以我们在数组末尾新增加以这个元素为结尾的子序列，否则当前元素值大于数组末尾值，那么我们可以通过二分的方法找到第一个比当前元素小的值（这种贪心的方法需要自己仔细分析一下，很容易得出），并用当前元素更新找到的那个值，也就是相当于把当前元素放在了找到的那个子序列的后面，最后数组的大小就是结果。

（2）：最少的下降子序列数目：同上，具体可以看下面的代码，有详细的注释

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> arr;
vector<int> tail;

int main(){
    int x;
    while(cin >> x) arr.push_back(x);
    //第一个答案是最长下降子序列 等价于 二分的方法就是找到的最少上升子序列的数量
    tail.push_back(0x3f3f3f3f);
    for(int i = 0;i < arr.size();++i){
        //此处的tail是一个单调下降的数组
        if(arr[i] <= tail.back())//此处有等号因为题意，要严格满足上升子序列，除非题意可以取得等号
            tail.push_back(arr[i]);
        else{
            //贪心：找到第一个比arr[i] 小的
            /*
            //方法一
            int l = 1, r = tail.size()-1;
            while(l < r){
                int mid = l + r>> 1;
                if(tail[mid] < arr[i]) r = mid;
                else l = mid + 1;
            }
            tail[l] = arr[i];
            */
            //方法二
            for(int t = 1;t < tail.size();++t)
                if(tail[t] < arr[i]){
                    tail[t] = arr[i];
                    break;
                }
        }
    }
    cout << tail.size()-1 << endl;

    //第二个答案是最少的下降子序列的数目 等价于 最长上升子序列的数目
    tail = vector<int>();
    tail.push_back(-0x3f3f3f3f);
    for(int i = 0;i < arr.size();++i){
        //此处的tail是一个单调上升的数组
        if(arr[i] > tail.back())//此处没有等号因为题意
            tail.push_back(arr[i]);
        else{
            //找到第一个比a[i] 大的
            int l = 1, r = tail.size()-1;
            while(l < r){
                int mid = l + r >> 1;
                if(tail[mid] >= arr[i]) r = mid;
                else l = mid + 1;
            }
            tail[l] = arr[i];
        }
    }
    cout << tail.size()-1 << endl;
    return 0;
}