wu :: forums - Print Page


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

        riddles >> cs >> Longest Oscillating Subsequence
        
(Message started by: joshi.prahlad on May 2^nd, 2011, 3:28am)

Title: Longest Oscillating Subsequence
Post by joshi.prahlad on May 2^nd, 2011, 3:28am

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.

Title: Re: Longest Oscillating Subsequence
Post by Grimbal on May 2^nd, 2011, 7:54am

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++;

Title: Re: Longest Oscillating Subsequence
Post by towr on May 2^nd, 2011, 8:40am

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.

Title: Re: Longest Oscillating Subsequence
Post by Grimbal on May 2^nd, 2011, 9:01am

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.

Title: Re: Longest Oscillating Subsequence
Post by joshi.prahlad on May 2^nd, 2011, 11:30pm

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.

Title: Re: Longest Oscillating Subsequence
Post by joshi.prahlad on May 2^nd, 2011, 11:57pm

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.

Title: Re: Longest Oscillating Subsequence
Post by towr on May 3^rd, 2011, 8:54am

on 05/02/11 at 23:30:57, 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.

Title: Re: Longest Oscillating Subsequence
Post by Grimbal on May 3^rd, 2011, 9:27am

It looks like it works (joshi.prahlad's idea), but it is O(n²).

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.