wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> find the sequence 
        
(Message started by: Sam on Sep 19^th, 2005, 4:09am)

Title: find the sequence
Post by Sam on Sep 19^th, 2005, 4:09am

Given any arbitrary array of size n containing random no.s .How will u find the longest monotonically increasing sequence . A monotonically sequence is one which may not
be contiguous and can contain any arbitrary increasing seq.

e.g if the array is

4,1,5,7,8,3,4,5,1,6,-2

The longest monotonically increasing seq. is 1,3,4,5,6
Give the optimized solution.

Title: Re: find the sequence
Post by Neelesh on Sep 19^th, 2005, 4:28am

The longest monotonically increasing subsequence can be obtained by dynamic programming. solution is essentially same as the solution of LCS : In this case we sort the original sequence and find LCS of the two (original and sorted)
Order : n²
Refer CLR for the exact algorithm. Another post on the same forum discusses LCS.

HOWEVER -
CLR also mentions that there is an O(n log n) algo to find longest monotonically increasing subsequence. (CLRS Edition 2, Problem 15.4-6)

I donot know how.

Title: Re: find the sequence
Post by towr on Sep 19^th, 2005, 4:29am

The easiest approach (or at least the first one that comes to mind) would be dynamic programming; O(n²) I think

Do you want strictly increasing? (Not that it makes a very big difference).

Title: Re: find the sequence
Post by Aryabhatta on Sep 19^th, 2005, 9:06am

on 09/19/05 at 04:28:51, Neelesh wrote:

CLR also mentions that there is an O(n log n) algo to find longest monotonically increasing subsequence. (CLRS Edition 2, Problem 15.4-6)

The O(nlogn) algorithm works as follows:

Let the array be A[1...n] i.e elements are A[1], A[2], .. , A[n], assume all are distinct.

(If they are not distinct we just consider the number to be the ordered pair (A[j],j) and do a lexicographic comparison)

Idea is to maintain for each k, the smallest element A[i_k] such that the maximum length monotone subsequence that ends at A[i_k] is of length k.

We can show A[i_k] < A[i_k+1]

Assume A[i_k] > A[i_k+1]
if i_k+1 < i_k then we have a sequence of length k+1 ending at A[i_k]

So assume i_k+1 > i_k
Let p₁, ..., p_k+1 = A[i_k+1] be a sequence of length k+1 ending at A[i_k+1]. Consider p_k. Clearly the max length subsequence ending at p_k is k. Also p_k < A[i_k+1] < A[i_k] which contradicts that A[i_k] is the smallest element which ends a max length k subsequence.

Thus A[i_k] < A[i_k+1]

Assume that we have maintained i₁, i₂, ... , i_m for the array A[1], A[2]..., A[n-1].

Consider adding A[n].

Find out where A[n] lies in the (sorted list) A[i₁], A[i₂], ... , A[i_m]

If A[i_t+1] > A[n] > A[i_t] set i_t+1 = n.

If A[n] > A[i_m] set i_m+1 = n

If A[n] < A[i₁] set i₁ = n

Note that we can maintain the i_k's (and A[i_k]'s) using a balanced binary tree, which gives an O(nlogn) algorithm if we start at A[1] and starting adding elements A[2], A[3] etc..

(insertion in balanced binary tree is O(logn), we insert at max n elements)

Title: Re: find the sequence
Post by Sam on Sep 19^th, 2005, 9:11pm

Hi Aryabhatt,

Can u explain your sol. with an example .

Title: Re: find the sequence
Post by Aryabhatta on Sep 21^st, 2005, 12:56pm

ok let us consider

1 8 2 7 3 6 4 5

Longest increasing is 1 2 3 4 5.

Start off with A[1] = 1.
For this array we get i₁ = 1.

Now add A[2] to the list
since A[2] > A[i₁]
we get i₂ = 2.

So the tree now contains 1 and 8.
Not we try to insert 2 into the tree.

2 lies between 1 and 8.
so we set i₂ = 3.
The tree now has 1, 2.
Now we insert. A[4] = 7.
Since 7 > 2
we set i₃ = 7.

Tree now has 1, 2, 7.
We insert A[5] = 3.
Since 2 < 3 < 7
we set i₃ = 5
Tree now has 1, 2, 3

Now insert A[6] = 6.

since 6 > 3.
we set i₄ = 6

Tree now has 1,2,3,6.

Now insert A[7] = 4.
since 3 < 4 < 6
we set i₄ = 7

Tree now is 1,2,3,4.

When we insert A[8] = 5.
we set i₅ = 8.

The final tree now has 1,2,3,4,5.

Note that in this case walking the tree gave you the right sequence, but that need not be true for all sequences. The algorithm I gave gives the length of the longest sequence, you will have to modify it to get the exact sequence.

Title: Re: find the sequence
Post by ji ryang chung on Oct 2^nd, 2005, 8:18pm

What if A = {3, 6, 1}?

Isn't that like follows?

initially, i1 = 1, A[i1] = 3
A[2] = 6 > A[i1] => i2 = 2
A[3] = 1 < A[i1](= 3) => i1 = 3???

I think the answer should be {3, 6}, right?

Title: Re: find the sequence
Post by ji ryang chung on Oct 2^nd, 2005, 8:30pm

I got it. Never mind the previous posting.
What we need is the longest subsequence, so tracking back the A[i] with the largest subscript will do.
Thanks for your tip, Aryabhatta!

Title: Re: find the sequence
Post by dav on Dec 7^th, 2005, 2:39am

Hi Guys,
Could you guys please help me in solving this problem

Iam trying to solve using dynamic programming.

a[] = {8,1,7,5,6}
b[]={1,5,6,7,8}

Assume there is array which stores the values:- D[m+1][n+1]

for i : 1 to m do
D[i][0] = 0

for i : 1 to n do
D[0][j] = 0

for i : 1 to m do
for j: 1 to n do

if(a[i] < b[j])
{
----
}
else
{
----
}

Please any body help me in doing this.

Title: Re: find the sequence
Post by dav on Dec 7^th, 2005, 2:51am

Hi Aryabhatt,

What if A ={8,1,7,5,6}

Title: Re: find the sequence
Post by dav on Dec 7^th, 2005, 11:54pm

Hi Guys,
I got the solution it same as LCS. Previously iam trying to do comparing the elements using "<". Now i got the solution

Title: Re: find the sequence
Post by Ved on Dec 9^th, 2011, 9:48pm

Since 7 > 2
we set i3 = 7.
should be
Since 7 > 2
we set i3 = 4.

on 09/21/05 at 12:56:05, Aryabhatta wrote: