最长不下降子序列

这里的注释说明更易理解

#include <bits/stdc++.h>
using namespace std;
const int MAXN = N;
int a[MAXN];
int d[MAXN];

int main()
{
    int n;
    cin>>n;
    for (int i = 1; i <= n; i++)
        cin>>a[i];
    if (n == 0) // 0个元素特判一下
    {
        cout<<'0'<<'\n';
        return 0;
    }
    d[1] = a[1]; //初始化
    int len = 1;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] >= d[len])
            d[++len] = a[i]; 
    //如果可以接在len后面就接上，如果是最长上升子序列，这里变成>
        else//否则就找一个最该替换的替换掉
        {
            int j = upper_bound(d + 1, d + len + 1, a[i]) - d; 
//找到第一个大于它的d的下标，如果是最长上升子序列，这里变成lower_bound
            d[j] = a[i];
        }
    }
    cout<<len<<'\n';
    return 0;
}

最长不上升子序列

同理，稍改。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = N;
int a[MAXN], d[MAXN];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n;i++)
        cin >> a[i];
    if(n==0)
    {
        cout << '0' << endl;
        return 0;
    }
    d[1] = a[1];
    int len = 1;
    for (int i = 2; i <= n;i++)
    {
        if(a[i]<=d[len])
            d[++len] = a[i];
        else
        {
            int pos = upper_bound(d + 1, d + 1 + len, a[i], greater<int>()) - d;
            d[pos] = a[i];
        }
    }
    cout << len << endl;
}

最长不下降子序列的内容

#include <bits/stdc++.h>
using namespace std;
int a[1000010], dp[1000010], poa[1000010],ana[1000010];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    dp[1] = a[1];
    int len = 1;
    poa[1] = len;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] >= dp[len])
        {
            dp[++len] = a[i];
            poa[i] = len;
        }
        else
        {
            int pos = upper_bound(dp + 1, dp + len + 1, a[i]) - dp;
            dp[pos] = a[i];
            poa[i] = pos;
        }
    }
    int t = len;
    for (int i = n; i >=1; i--)
    {
        if (!len)
            break;
        if (poa[i] == len)
            ana[len] = i,len--;
    }
    for (int i = 1; i <= t; i++)
        cout << a[ana[i]] << " ";
}