|
fani vafeiadou <fani_vafeiadou@hotmail.com> wrote in message <3676195.1233871866511.JavaMail.jakarta@nitrogen.mathforum.org>...
> .......
> i have the following task:
> we should write a program, which computes the longest increasing subsequence in a given sequence,
> ......
Because it seems a little unfair to assign this kind of homework problem to students in marketing, I am willing to give you some limited assistance as to its solution, Fani.
The key to solving it in an efficient manner is this. (I am assuming here that all elements are distinct; if not, the needed adjustment is easily made.) As a first step, start at the first element of the given initial sequence and collect all elements which are the smallest element up to that point. That is, in your example of [8 9 2 10 3 7 4 1 5 6] it would be [8 2 1]; each of these is the smallest element encountered up to that point in the original sequence. Another way of saying this is that each of the other elements not among these three have the property that there exists an element in [8 2 1] which is both earlier and smaller. It requires only a single pass through the initial sequence to find this subsequence.
Now remove these elements from the initial sequence. In the example it would leave behind only the seven elements [9 10 3 7 4 5 6]. Then repeat this process on this smaller sequence, arriving at [9 3], and leaving [10 7 4 5 6]. At the third such step you get [10 7 4] leaving [5 6]. At the fourth step you get just [5], leaving [6]. At the fifth step you get just [6] leaving an empty set. Now you have successfully partitioned the original example sequence into a set of six disjoint subsequences:
[8 2 1], [9 3], [10 7 4], [5], and [6]
At this point you are entitled to conclude both that there must exist an ascending subsequence with 5 elements and that that is the longest such sequence possible.
As to finding such a longest subsequence, recall that all the elements outside of [8 2 1] have the property that an element exists in [8 2 1] which is earlier and smaller, and in particular this applies to elements of the next set [9 3]. This also holds true for all pairs of consecutive partitioned subsequences. For each element of a partitioned sequence there exists an element somewhere in the previous partition that is earlier and smaller. Starting with 6 and working backwards, the previous 5 must be chosen. From 5 only the 4 in the previous set [10 7 4] is possible. Continuing this, you arrive at the subsequence [2 3 4 5 6] which in this case is the only one possible. In general there may be a number of choices along the way.
For each step in this backwards process at an element selected in that partition, there will have to be a scan searching for an earlier and smaller element in the previous partition set. You know there has to be at least one to be found at each step. That means a scan for each partitioned set.
All told, you are faced with twice the number of scans as there are partitions, once for the forward process and once for the backwards process.
As you will have guessed by now, I have left all the details of implementing such a procedure to you. It will not be a trivial thing to write, but for long initial sequences it is unlikely in my opinion that any other basic kind of algorithm would be able to match one along these lines for efficiency.
Roger Stafford
|
Feed for this Thread