DP --- Longest Nondecreasing Subsequence

1. Classical DP, finding the longest nondecreasing subsequence can also used in like string matching, analyzing card games.
The point is to remember the length of previous longest subsequence at each point.
This method gives O(N^2) complexity, since for each n, we need to check all previous values length, then find the maximum

2. This method is O(NlogN). Basic idea is to keep a array to store the longest subsequence, if the A[i+1] is bigger than all then put it at behind, if A[i+1] is not bigger than all then update it in the subsequece, since it forms a non-decreasing subsequence, although not have the length of the array.

Code:

int longestSub(const vector &A)
{
    vector tail_value;
    for(const int &a : A)
    {
        auto it = upper_bound(tail_value.begin(), tail_value.end(), a);
        if (it == tail_value.end()) tail_value.push_back(a);
        else   *it = a;
    }
    return tail_value.size();
}