LIS, Longest Increasing Subsequence for short.
LCS, Longest Common Subsequence for short.
LPS, Longest Palindrome Subsequence for short.(Ps, I don't konw if it's an official name.)
There're many problems on Codeforces are about these classical problems, such as 335B,340D and so on. Let's discuss the algos to solve all these prolems.
Note that, we'd like to count the length of the sequence and also we want to get a valid subsequence of the original sequence.(maybe the leftest one, or that has the smallest alphabet order.sorry for my poor English.)
As far as I know, LIS can be sloved in O(nlogn). algo goes like this. For example, 2 1 5 4 3 7 8 6 9, we can use a array to save the LIS we can get until now, and every time we come up with a new number. We find the leftest number which if smaller than it, and replace the next one with the num we have right now. array changes like this:
2 -> 1 -> 1 5 -> 1 4 -> 1 3 -> 1 3 7 -> 1 3 7 8 -> 1 3 6 8 -> 1 3 6 8 9.
So, length we want is 5. And you can check it out.(2 5 7 8 9 is an valid subsequence with length 5.) this algo runs in O(nlogn). Use binary search (you can use lower_bound() in STL in convenience.)to find the right place where we want to put the number we have right now.
What I know is so limited, so be my guest and share your ideas to these problems.(Ps, I don't know how to find a valid subsequence of the problem above, as you can see, the alog doesn't give the right subsequence we want.)
Thank you sincerely. And I'm sorry that I don't konw how to make this blog look more neatly rather than all the words gathered together, though I have tried all my best to tap the end of line, however when it was posted, it doesn't work. I'm not very familiar with this skills.(If you can help me with this problem, that will be lovely!)
I find a way to get an valid LIS.(can be leftest one or any valid one) Using the same example. We need another array to save the information we need. c[i] is used to save the place a[i] can be in the LIS.(i start from 1)Algo goes like this:
2 -> 1 -> 1 5 -> 1 4 -> 1 3 -> 1 3 7 -> 1 3 7 8 -> 1 3 6 8 -> 1 3 6 8 9
a[i]: 2 1 5 4 3 7 8 6 9
c[i]: 1 1 2 2 2 3 4 3 5
And then we can use c[i] to get the sequence we want. Let len be the length of LIS.We start at the end of c[i].And find the first i that c[i] == len. And we push a[i] into a stack, and pre = a[i], then len--, and when len != length of LIS, we find the first i that c[i] == len and a[i] > pre, do the same thing until len == 0. And we just need to pop all the element in the stack. In the example, we do as follow: 9 8 7 3 1, and 1 3 7 8 9 is a valid LIS. To get the leftest one, everytime wo need to get the leftest i that c[i] == len && a[i] < pre.
You may doubt that will there be a situation that in one step we don't save the leftest one and in the latter step we can get lefter solution? And I think I can prove that is impossible.
Supposing in a step we can find many i that c[i] == len and a[i] < pre. We choose two of them x and y, so that c[x] == c[y] == len, and x < y, but suppose we don't choose x, we choose y, because in the following step (it just affact the exact the step followed) we can get a lefter solution. So there should be some inequation holds. Let z be the id if i we choose in the follow step, so c[z] == len-1, and a[y] > a[z] and a[x] < a[z](otherwise we x, y both can get the "lefter" solution, that's a controdiction.) So what do we get? x < y but a[x] < a[z] < a[y], so a[y] > a[x] && y > x both holds. That is impossible !!! Because why don't we add both y and x to the LIS to make it longer rather than add just one of them to the LIS. So we are done. Am I right ? If there was any mistakes, just point it out. And how about LCS and LPS, I think LPS can changed into LCS problem if use the same algo, and as far as I know, LCS also can be solved in O(nlogn), so LPS can be solved in O(n^2logn). Any ideas? Any faster solutions? Let's just discuss here. ^_^
Oh, it looks horrible!!!! How to devide it into some separate paragraph? T^T.... It may help others to read. Any one help me?
Did you try pressing enter 2 times?
Edit. Here is the new paragraph.
Thank you. It's working now. Perfect!