longest ordered sequence problem

[hardworking]

I have a problem as follows:
There is an array which is unordered, how to find its longest ordered sequence.
for example, an array 1,3,7,4, the needed sub sequence is 1,3,4.
thanks!

[Luchin_plusplus]

O'key, altough I don't know of an exact algorithm to solve your poblem, I can divide it into 4 tasks:

1.- Find a pair of contiguous, ordered, elements.
2.- Extend the range of the ordered elements until you find an element that breaks the order.
3.- Do the same to collect all ranges into your sequence.
4.- Select the one with lasgest size.

To solve (1), just use an algorithm to find two ordered and contiguous elements. This should take linear time in the size of your sequence. Then, preserve the starting point of the range (the first element of the ordered pair), and extend the range by comparing forwards each element against the previous one (the first comparison is trivial). You will end in a element of the sequence that breaks the order. The previous element (which was in order in the range) will become the "end" of your range.
To solve (3), take the index of the element that broke your order in (2), and continue step (1) from that point. You will end when you reach the last element in your sequence, and you will get a list of indexes [start, end], that determine ordered subsequences.
To solve (4), just select the index pair that contains the greater number of elements. This is a trivial sorting of the sizes of the ranges.

For an example, in your array:
1, 3, 7, 4

Step 1 would find the pair (1,3) at index 1. Step 2 would "walk" the array comparing (3, 7) and (7, 4); until it finds the pair (7,4), which is unordered. Thus the last element of the subsequence would be 7, and the first one would be 1, which is determined by indexes 1 and 3.
Step 3 would do nothing, because the array ends with index 4 (4) and thus no more comparisons are necesary.
Step 4 would select your unique range [1,3] that covers elements (1, 3, 7) and has size 3. Thus this is the largest ordered sequence.

Hope this "procedure" can help.

Bye!

[Yves M]

This problem has been studied before, and the best solution is to use dynamic programming approach.

You have 2^N possible subsequences, which means that you can rule out checking all of them, because that would be prohibitively slow. The dynamic programming approach basically means that you find the longest ordered subsequence(s) for a[0]...a[m-1] and then, along with element a[m], you compute the longest subsequences for a[0]...a[m].

There is a pretty good explanation on this webpage. (http://home.tiac.net/%7Ecri/2001/mlas.html)

[hardworking]

Thank you very much.
I find this problem in the chapter of dynamic programming at an algorithm book. It requires an O(n**2) method then an O(n*lgn) method. I don't know how to work it out. I consider that the key is to find the solution's structure and define a recurrence according the step of dynamic programming.

[Yves M]

[ edited ]
When you are at element a[m], you have a list (L={S1, S2, S3, ...} of all the longest minimal ordered subsequences in a[0]...a[m-1]. Each of the subsequences is characterized by its highest element and its length. Now, when you consider to which subsequence you should add a[m] to, you should select the longest one to which it can be added. At this point, you can discard the shorter subsequences to which it could be added. If you can't add it to any of the subsequences, you just start a new subsequence with this element (since it will be smaller than the top elements in the sequences in L).

Of course, implementation is a different story. If you wanted to keep the list of subsequences explicitly, it could very well get memory intensive and slow. The key to having a good optimization is to note that you are only interested in *any* longest subsequence, so you can just as well select the one with the minimal elements. This means that every element in a[0] ... a[m-1] belongs to at most one subsequence. If a[k] would belong to two subsequences, then the two subsequences would either be of equal length (in which case you are not interested in having both, the minimal will suffice) or one would be longer than the other. But if one would be longer, then you could just discard the shorter one, because any ordered subsequence after a[k] has to have elements bigger than a[k].

In pratice this means that for each a[k], you can just keep a pointer to the previous element in that subsequence. So you can store all the "temporary" subsequences in another array with N back-pointers. Then you also need some storage to keep the indexes of the elements which end a particular subsequence (also O(N)) and you have all the data you need.

[hardworking]

It's so kind of you to answer my questions. would you recommend me some good web resource for data structure and algorithm ? thanks

[Yves M]

To be honest, I think books are a better way to learn about this. They can be expensive, so maybe try to locate them in a library near you. The reference is Donald Knuth's "The Art Of Computer Programming". I also like Robert Sedgewick's "Algorithms in C++" which is a bit easier to read.