题解 | 最长不下降子序列

在旧的最长子序列长度的基础上，将新的更小的元素放入其中，既保证旧的最长长度得到记录，同时为未来可能出现的更长长度创造可能性

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

int main() {
    int n;
    cin >> n;
    vector<int> s(n+1, 0);
    // 6 9 1 2 6 2 1 4 5
    // 6 
    // 6 9 
    // 1 9
    // 1 2
    // 1 2 6
    // 1 2 2
    // 1 1 2
    // 1 1 2 4
    // 1 1 2 4 5
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    vector<int>d;
    d.push_back(s[1]);
    for (int i = 2; i <= n; i++) {
        if (s[i] >= d.back()) {
            d.push_back(s[i]);
        }
        else {
            *upper_bound(d.begin(), d.end(), s[i]) = s[i];
        }
    }
    cout << d.size();
    
}