Longest non-decreasing subsequence - TC: O(nlogn)

int longestNonDecresingSubsequenceLength(vector<int> a) {

    vector<int> s;

    s.push_back(a[0]);

    int n = a.size();

    int len = 1;

    for (int i = 1; i < n; i++) {

        int idx = upper_bound(s.begin(), s.end(), a[i]) - s.begin();

        int m = s.size();

        if (m > idx) {

            s[idx] = a[i];

        } else {

            s.push_back(a[i]);

        }

    }

    return s.size();

}