Author |
Topic: find the sequence (Read 3859 times) |
|
Sam
Newbie
Posts: 30
|
 |
find the sequence
« on: Sep 19th, 2005, 4:09am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
Neelesh
Junior Member
Gender: 
Posts: 147
|
|
Re: find the sequence
« Reply #1 on: Sep 19th, 2005, 4:28am » |
Quote Modify
|
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 : n2
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: find the sequence
« Reply #2 on: Sep 19th, 2005, 4:29am » |
Quote Modify
|
The easiest approach (or at least the first one that comes to mind) would be dynamic programming; O(n2) I think
Do you want strictly increasing? (Not that it makes a very big difference).
|
| « Last Edit: Sep 19th, 2005, 4:33am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: find the sequence
« Reply #3 on: Sep 19th, 2005, 9:06am » |
Quote Modify
|
on Sep 19th, 2005, 4:28am, 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[ik] such that the maximum length monotone subsequence that ends at A[ik] is of length k.
We can show A[ik] < A[ik+1]
Assume A[ik] > A[ik+1]
if ik+1 < ik then we have a sequence of length k+1 ending at A[ik]
So assume ik+1 > ik
Let p1, ..., pk+1 = A[ik+1] be a sequence of length k+1 ending at A[ik+1]. Consider pk. Clearly the max length subsequence ending at pk is k. Also pk < A[ik+1] < A[ik] which contradicts that A[ik] is the smallest element which ends a max length k subsequence.
Thus A[ik] < A[ik+1]
Assume that we have maintained i1, i2, ... , im 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[i1], A[i2], ... , A[im]
If A[it+1] > A[n] > A[it] set it+1 = n.
If A[n] > A[im] set im+1 = n
If A[n] < A[i1] set i1 = n
Note that we can maintain the ik's (and A[ik]'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)
|
|
IP Logged |
|
|
|
Sam
Newbie
Posts: 30
|
|
Re: find the sequence
« Reply #4 on: Sep 19th, 2005, 9:11pm » |
Quote Modify
|
Hi Aryabhatt,
Can u explain your sol. with an example .
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: find the sequence
« Reply #5 on: Sep 21st, 2005, 12:56pm » |
Quote Modify
|
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 i1 = 1.
Now add A[2] to the list
since A[2] > A[i1]
we get i2 = 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 i2 = 3.
The tree now has 1, 2.
Now we insert. A[4] = 7.
Since 7 > 2
we set i3 = 7.
Tree now has 1, 2, 7.
We insert A[5] = 3.
Since 2 < 3 < 7
we set i3 = 5
Tree now has 1, 2, 3
Now insert A[6] = 6.
since 6 > 3.
we set i4 = 6
Tree now has 1,2,3,6.
Now insert A[7] = 4.
since 3 < 4 < 6
we set i4 = 7
Tree now is 1,2,3,4.
When we insert A[8] = 5.
we set i5 = 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.
|
|
IP Logged |
|
|
|
ji ryang chung
Guest
|
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?
|
|
IP Logged |
|
|
|
ji ryang chung
Guest
|
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!
|
|
IP Logged |
|
|
|
dav
Newbie
Gender:
Posts: 47
|
|
Re: find the sequence
« Reply #8 on: Dec 7th, 2005, 2:39am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
dav
Newbie
Gender:
Posts: 47
|
|
Re: find the sequence
« Reply #9 on: Dec 7th, 2005, 2:51am » |
Quote Modify
|
Hi Aryabhatt,
What if A ={8,1,7,5,6}
|
|
IP Logged |
|
|
|
dav
Newbie
Gender:
Posts: 47
|
|
Re: find the sequence
« Reply #10 on: Dec 7th, 2005, 11:54pm » |
Quote Modify
|
Hi Guys,
I got the solution it same as LCS. Previously iam trying to do comparing the elements using "<". Now i got the solution
|
|
IP Logged |
|
|
|
Ved
Junior Member
Gender:
Posts: 53
|
|
Re: find the sequence
« Reply #11 on: Dec 9th, 2011, 9:48pm » |
Quote Modify
|
Since 7 > 2
we set i3 = 7.
should be
Since 7 > 2
we set i3 = 4.
on Sep 21st, 2005, 12:56pm, Aryabhatta wrote: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 i1 = 1.
Now add A[2] to the list
since A[2] > A[i1]
we get i2 = 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 i2 = 3.
The tree now has 1, 2.
Now we insert. A[4] = 7.
Since 7 > 2
we set i3 = 7.
Tree now has 1, 2, 7.
We insert A[5] = 3.
Since 2 < 3 < 7
we set i3 = 5
Tree now has 1, 2, 3
Now insert A[6] = 6.
since 6 > 3.
we set i4 = 6
Tree now has 1,2,3,6.
Now insert A[7] = 4.
since 3 < 4 < 6
we set i4 = 7
Tree now is 1,2,3,4.
When we insert A[8] = 5.
we set i5 = 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.
|
|
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove