A problem about Longest Increasing Subsequence

[zqzas]

Hello everyone!
I have a difficult problem for me:

Longest Increasing Subsequence may be familier to us.But there is an advanced question.That is how to find wheather there is a increasing subsequence of length L.If there is more than one ,just output the first one in dictionary order.
We have to find a fast algo at least O(NlogN) where N is the length of the sequence.


Thx!

[SlickHawk]

Well, if you have an algorithm to find the longest increasing subsequence (which is already O(n*lg(n))), and it turns out that the size of the subsequence returned is >= L, then any possible subsequence of THAT is also a valid subsequence of the initial set.

Now if what you're looking for is a subsequence N of size L such that N is not a subsequence of any other strictly increasing subsequence (mouthful), that's a bit different.

What you could do is run the LIS algorithm, and if L < S (where S is the size of the subsequence the LIS just returned), you remove all those elements from the input list and repeat. If L == S, you've found what you're looking for. If S < L, there exists no subsequence.

Since you no longer iterate once S < L, each time you'll be removing at least L + 1 elements from the list, meaning at worst you iterate N / L times. Each time you're running LIS, however, so it ends up being O((N^2 / L) * lg(N)), or O(n^2), which is not what you're looking for.

Anyway, just letting you know, but if what you're looking for is the second thing, there cannot possibly be more than one subsequence of length L unless they're the exact same sequence and you don't count equal elements to be increasing, as in...

1, 1, 2, 2, 3, 3.

[zqzas]

"5 1 2 6"

There are several length 2 subsequences,but "1 2" is the one we want
In dictionary order "1 2" < "1 6" <" 5 6"

[SlickHawk]

Ah, I see what the problem is then. I realize I was incorrect before, there may be several unique subsequences of length L. For example,

1, 3, 2, 5

(1, 2, 5) and (1, 3, 5) are both valid Increasing Sequence subsequences of length 3 that are not subsequences of another Increasing Sequence. If you run LIS on the initial sequence, you'll most likely get (1, 3, 5), which won't give you the (1, 2) you're looking for (assuming you're looking for sequences of length 2.

So now I'm not sure. If you can somehow rework the standard algorithm to find all LISes by not discarding old data, then you could find the first one in dictionary order fairly easily. But I'm not sure if that can be done without increasing the complexity.

Sorry for not being able to help.