Hi everyone! I want to share a very cute LIS(Longest Increasing Subsequence) implementation.
I found it on here.
Also thanks to mnbvmar for improve the implementation.
But this assumes no duplicates in array.
set < int > s;
set < int > :: iterator it;
...
FOR(i, 1, n)
{
s.insert(a[i]);
it = s.upper_bound(a[i]);
if(it != s.end())
s.erase(it);
}
cout << s.size() << endl;
So I changed it to multiset, for duplicate.
multiset < int > s;
multiset < int > :: iterator it;
...
FOR(i, 1, n)
{
s.insert(a[i]);
it = s.upper_bound(a[i]);
if(it != s.end())
s.erase(it);
}
cout << s.size() << endl;
There are seems work, and it's easy to proof them.
Thanks for your reading :)
UPD : I just found a similar approach for Longest Strictly Increasing Subsequence.
multiset < int > s;
multiset < int > :: iterator it;
...
FOR(i, 1, n)
{
s.insert(a[i]);
it = s.lower_bound(a[i]);
it++;
if(it != s.end())
s.erase(it);
}
cout << s.size() << endl;
UPD2 : You can solve LMIS(LIS) and ELIS(LSIS) with this approach.
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 byfind
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 toa[i]
). So it should be likewhat if we need to print the lis?
Ignore ...
Actually it's not true. Look at this example we have : 1 1 0 10 3
S contains : 0 1 3
Actually i-th element in the set is the least value for end of LIS of length i(or i+1 if you think zero-based). If you think i am wrong please tell me.I am not very sure.
edit:a typo corrected
Ignore...
Guys, think twice before you post misleading comments.
Again, not true, take a look at 2, 3, 1. The sets contain numbers 1,3, which is not a valid subsequence.
I'm not sure if it's straightforward to recover the subsequence from this approach, anybody a clue?
Sure, it can be done. The code becomes a bit longer because instead of storing just the values you have to store the indices.
In the simple code, you have the following invariant after processing each element: Consider the values currently stored in the set S, in increasing order. Let's call them S[0], S[1], S[2], etc. Then, for each i, S[i] is the smallest value such that the sequence we already processed has an increasing subsequence of length i+1 that ends in the value S[i].
If you want to reconstruct the sequence, you have to remember indices of those values instead of the values themselves. Then, whenever you insert a new index x into the position i, you look at the index currently at position i-1 in the set and remember it as the previous element of the optimal sequence that ends at index x.
Here is a sample implementation. The function returns the indices of elements that form one possible longest strictly increasing subsequence of the input. (The input is assumed to be non-empty. It is allowed to contain duplicates.)
It's much easier if the input is guaranteed to have no duplicates. In that case, just use a map and for each value remember the immediately preceding one in an optimal solution.
i have never seen a piece of code like this. can u explain what it does?
It's a lambda function. It's an anonymous function with a few abilities (for example, it can access every variable that is given to it as parameter and every variable that's visible from the point of definition).
Why is it better to use lambdas? If you want to sort a vector of ints by increasing value of x3 + 17x, you can just write
...instead of some boring and lengthy defining new comparison functions etc.
In the example above the advantages are even a bit larger — when not using lambdas, you would have to write a functor (way 1 here: http://ideone.com/191tt3) that is as long as a function where we use it! Lambda is way more concise — and moreover, we can define it exactly where we need it (if the function was 200 lines long, we wouldn't have to scroll up above this function to find the comparators!).
A very underrated coment by mnbvmar
Print all elements of set :/
ignore...
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 bea[i]
)It looks like magic, why does it works?
It's itself of magic!
Forget it is a (multi)set, think of it as a simply vector (look at my comment). When you insert a value
x
at positioni
it means that there exists a LIS ending withx
has lengthi
. Furthermore, ifmagic[i] = x
it meansx
is the smallest value which can end a LIS of lengthi
. Sketch of proof by induction:What you do (with
lower_bound
function) is you look for the first indexi
such that the numbermagic[i-1]
is less thanx
. By induction it means that there is a LIS ending withmagic[i-1]
of lengthi-1
and it's the "smallest" one. So you can extend it by one obtaining a LIS of lengthi
and it will also be the "smallest" one (i.e. ending with the smallest number).But it does NOT mean, that the vector contains a valid subsequence.
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.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 positioni
, it was once added to themagic
vector at positioni
. 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 vectorshistory[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
I think that my code is better.
Construct F[i] and output LIS length (max element in array F):
If we need to output the sequence, add this code:
It's hard to say which code is "better" (afaik there is no order on codes based on their quality) :) But indeed, your solution is shorter. Thank you for the feedback, I really like it!
Nice implementation
But can I reconstruct the LMIS array in O(LIS.size) ?
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; }
Beautiful implementation!
Can anyone tell me why this is correct ?
you'd better know LIS using binary search first
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,
This finds a strictly-increasing LIS, but you can easily modify it to find longest nondecreasing sequences by changing
lower_bound
toupper_bound
.Code in my comment above is 2 lines shorter and does the same thing.
But you need to fill v with infinities.
Sorry for asking a stupid question :(
It's from 5 years ago and just an another implementation. So many people already knew vector approach so that's why nobody didn't mention it.
Also in my solution, you do not even need to use a vector for that implementation, a set works fine(and is shorter).
Use BIT
Use BIT
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)
Sorry to Necropost, but my G, do you know what the word "increasing" means?
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)$$$.
Make list of list(like in graph) say it $$$G$$$. Now add all pair(a[idx],idx) to list $$$G[j]$$$ where $$$j$$$ is length of largest possible subsequence ending with $$$a[idx]$$$. After this construction we can use $$$dp$$$ with prefix sum and Binary search to find the answer.