Author |
Topic: Longest Oscillating Subsequence (Read 7776 times) |
|
bazinga
Junior Member
Gender: 
Posts: 53
|
 |
Longest Oscillating Subsequence
« on: May 2nd, 2011, 3:28am » |
 Quote  Modify
|
Call a sequence X [1 .. n] of numbers oscillating if X [i] < X [i + 1] for all even i, and
X [i] > X [i + 1] for all odd i. Describe an efficient algorithm to compute the length of the
longest oscillating subsequence of an arbitrary array A of integers.
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Longest Oscillating Subsequence
« Reply #1 on: May 2nd, 2011, 7:54am » |
Quote Modify
|
I think you just need to scan the numbers from left to right and count how many times the difference changes sign.
count = 1;
sign = +1;
for i = 2 to n
if a[i]<a[i-1] and sign>0
count++;
sign = -1;
if a[i]>a[i-1] and sign<0
count++;
sign = +1;
which can be optimi-obfuscated to
count = 1;
for i = 2 to n
if count%2==1 ? a[i]>a[i-1] : a[i]<a[i-1]
count++;
|
| « Last Edit: May 2nd, 2011, 8:11am by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Longest Oscillating Subsequence
« Reply #2 on: May 2nd, 2011, 8:40am » |
Quote Modify
|
I think he means the more interesting case where the X[i] aren't necessarily consecutive in the source array.
In which case I'd opt for dynamic programming.
|
| « Last Edit: May 2nd, 2011, 1:19pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Longest Oscillating Subsequence
« Reply #3 on: May 2nd, 2011, 9:01am » |
Quote Modify
|
I mean the same.
By subsequence, I mean: write down the A's, erase some, renumber the rest without changing the order.
I believe the longest oscillating sequence consists of the local extrema.
|
|
IP Logged |
|
|
|
bazinga
Junior Member
Gender:
Posts: 53
|
|
Re: Longest Oscillating Subsequence
« Reply #4 on: May 2nd, 2011, 11:30pm » |
Quote Modify
|
Thanks,Grimbal. I am unclear about how we will find the longest sub-sequence by extending this approach
e.g. In this array {15,10,25,5,7,35,10,45}
the longest sub-sequence would be 15,10,25,5,35,10,45 with length 7
while the ur algorithm would count 15,10,25,5,7 and then 35,10,45 which will also result in "count" becoming 7.
But I am not sure how to extend it to get the longest sub-sequence.
|
|
IP Logged |
|
|
|
bazinga
Junior Member
Gender:
Posts: 53
|
|
Re: Longest Oscillating Subsequence
« Reply #5 on: May 2nd, 2011, 11:57pm » |
Quote Modify
|
The approach I had in mind was
Begin from the end of the array and maintain two variables
1.even length -which is the length of subsequence if this element comes at an even position.
2.odd length is the length of the subsequence if this element comes at an odd position.
Set the even and odd length of all the array elements to 1.
Beginning from the end of the array for an element a[i] scan all the elements a[j] where j>i
if a[j] <a[i] then
set the odd length of a[i] = max(oddLength(a[i]),evenLength(a[j])+1)
if a[j]>a[i] then
set the even length of a[i] = max(evenLength(a[i]),oddLength(a[j])+1)
return the maximum oddLength found so far.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Longest Oscillating Subsequence
« Reply #6 on: May 3rd, 2011, 8:54am » |
Quote Modify
|
on May 2nd, 2011, 11:30pm, joshi.prahlad wrote:| But I am not sure how to extend it to get the longest sub-sequence. |
|
If you want to do more than just measure the length, store the extrema instead of only counting them.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Longest Oscillating Subsequence
« Reply #7 on: May 3rd, 2011, 9:27am » |
Quote Modify
|
It looks like it works (joshi.prahlad's idea), but it is O(n2).
To find the longest subsequence (or one of the longest), do the following.
- take the 1st element such that the next one is smaller (or you reach the end of the array)
- take the 1st element after that such that the next one is larger (or the end of the array).
- restart until A is used up.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print