参考acwing.1010
题中求解两个问题：
1.最长不上升子序列的最大长度
2.最少要多少个最长不上升子序列可以覆盖整个区间
其中问题2等价于求区间中最长上升子序列的长度

1.数据量小于1000可以用dp来写
2.数据量为1e5,用贪心求解

下面附上两个的代码：

贪心

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 1010;
int g[N];
int q[N];
int w[N];
int n,len;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    while(cin>>w[n]) n++;

    len = 0;
    for (int i = n-1; i >=0; i -- )//反向求最长不下降子序列等价于求最长不下降子序列
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = (l + r + 1) >> 1;
            if (q[mid] <= w[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = w[i];
    }

    cout<<len<<endl;

    int len = 0;
    for (int i = 0; i < n; i ++ )
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = (l + r + 1 )>> 1;
            if (q[mid] < w[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = w[i];
    }

    cout<<len<<endl;



    return 0;
}

dp

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

const int maxn = 1005;
int n, a[maxn];
int f[maxn], g[maxn];

int main()
{
    while(cin >> a[n]) n ++;
    int ans1 = 0;
    int ans2 = 0;
    for(int i = 0; i < n; i ++)
    {
        f[i] = 1;
        g[i] = 1;
        for(int j = 0; j < i; j ++)
        {
            if(a[i] <= a[j]) f[i] = max(f[i], f[j] + 1);
            else g[i] = max(g[i], g[j] + 1);
        }
        ans1 = max(ans1, f[i]);
        ans2 = max(ans2, g[i]);
    }
    cout << ans1 << endl;
    cout << ans2 << endl;
    return 0;
}