It may not work now depending on your luck and multiset implementation (but there's an easy workaround). I assume we're talking about a longest non-decreasing sequence.

For example, take 1 3 1 2. After two first steps S is obviously {1,3}. After third insert it's {1,1,3}. However, you have no control over which one (literally, 1) gets selected by find routine. If it's second one, everything is OK (it's {1,1}, that is the LIS of the first three elements), however if it finds the first one, the second element gets deleted and we end up with incorrect set {1,3}. In first case, we find a correct longest non-decreasing sequence of length 3, in second case we find only the one with length 2.

It means we should modify the search a bit. We should look for the first position containing the value bigger than a[i] (and not, as before, the next position after any value equal to a[i]). So it should be like

FOR(i, 1, n){
    S.insert(a[i]);
    it = S.upper_bound(a[i]);   // this does exactly what I said
    if(it != S.end()) S.erase(it);
}

what if we need to print the lis?

What is x in the second code? It is fixed now!Thanks!

http://ideone.com/Vzvbyu

in first two code snippets, what is x? (i think it should be a[i])

It looks like magic, why does it works?

Further explanation can be found here: http://stackoverflow.com/questions/18559186/longest-incresing-subsequence-using-stdset-in-c

JuanMata, Mr.ink, thanks, fixed.

I would like to share my solution, which can be extended to recover the LIS (the // OPTIONAL part). My solution works for Longest Strictly Increasing Subsequence, however it is a matter of some minor changes to make it work for the other version. I am sorry for using some C++ 11 tricks, but it's more convenient and readable for me.

int solve(vector<int> input, vector<int>& solution)
{
    vector<int> magic;
    vector< vector<int> > history; // OPTIONAL
    for (int x: input) {
        vector<int>::iterator it = lower_bound(magic.begin(), magic.end(), x);
        if (it == magic.end()) {
            magic.push_back(x);
            history.push_back(vector<int>(1, x)); // OPTIONAL
        }
        else {
            *it = x;
            history[it-magic.begin()].push_back(x); // OPTIONAL
        }
    }
    
    // OPTIONAL
    {
        int result = magic.size();
        solution.resize(result);
        solution.back() = magic.back();
        for (int i=result-2; i>=0; i--) {
            auto it = lower_bound(history[i].rbegin(), history[i].rend(), solution[i+1]);
            it --;
            solution[i] = *it;
        }
    }
    
    return magic.size();
}

A short comment on the code:

Instead of a (multi)set I use simply a vector.

For recovery, I use the following fact: if some number x is in the optimal subsequence on position i, it was once added to the magic vector at position i. This is why I record the history of all numbers which were inserted on each position in the vector. Then I traverse this structure from the end to the beginning and select the appropriate number. It requires several simple lemmas to prove it works: e.g. all vectors history[i] are sorted by both value (reverse order) and position in the input sequence!

Edit: I can see my solution (its basic part) is equivalent to dalex's solution in this comment

LIS IMPLEMENTATION

ll lis(vector &vec){ ll an=0,n=vec.size(); n++; ll arr[n]; arr[0]=-1e9; repp(i,1,n)arr[i]=1e9; rep(i,n-1){ ll pos=upper_bound(arr,arr+n,vec[i])-arr; an=max(an,pos); arr[pos]=vec[i]; } return an; }

Can anyone tell me why this is correct ?

yeah really cute i love this it's very simple

This is an old post, but it seems no one has explicitly mentioned yet that you do not need to use a set or multiset for this implementation, a vector works fine (and can be faster). For example,

vector<int> v;
for (int i = 0; i < n; i++) {
    auto it = lower_bound(v.begin(), v.end(), a[i]);
    if (it != v.end()) *it = a[i];
    else v.push_back(a[i]);
}
return v.size();

This finds a strictly-increasing LIS, but you can easily modify it to find longest nondecreasing sequences by changing lower_bound to upper_bound.

Use BIT

How can this be used in the case of pairs?

What if the input array is a = [ 8, 2, 2, 1] Answer is 2 (2,2) but algorithm gives (1,2)

Just to make this blog little more useful — We can also find total no of $$$LIS$$$ (of all version increasing/non-increasing...) in $$$O(nlogn)$$$.