Friday, April 11, 2014

Find the longest oscillating subsequence

Given the sequence of numbers find the longest oscillating subsequence

Solution
The oscillating sequence is the sequence, when the 2 adjacent numbers are either greater than or smaller than the current number. So, for example following is the oscillating sequence:
1, 7, 4, 6, 2
So, 7 is greater than both 1 and 4, 4 is less than both 4 and 6 and so on.

Now, given the sequence of number we have to find the longest oscillating subsequence. Note that subsequence is not the contiguous list of elements, but only thing is they should occur in same order.

So, for example consider the sequence 1, 7, 8, 4, 3, 1...What is the longest subsequence?
Answer is 1, 7, 4 OR 1,8, 4, OR 1,8,3 OR 1,7,3 .. and the size is 3. So, we have to find any of the longest subsequence.

Here is the pseudo code following greedy algo:
Initialize counter = 1 to keep length of subsequence, List = {}

foreach (element in the input sequence){
  If next element is greater than previous element{
         find the next local maxima,
     else
         find the local minima
         
     if(foundLocalMaxima){
         increment the counter to 1.
         List.add(localMaxima)
     }
     else if(foundLocalMinima){
         increment the counter to 1.
         List.add(localMinima)
     }       
           
}

Lets take the example - 1 4 6 7 6 3 1 2
  1. We start with 1, counter =1, list = {1}.
  2. 4 is greater than 1, we will increment counter by 1. Now, as 6 is greater than 4, we will continue to next element. Now 7 is a local maxima, as it is greater than 7 we will add it to the list and increment the counter.counter = 2, list {1,7}
  3. Now we 1 is the next local minima, and hence add it to list and increment the counter.
    list = {1,7,1} and counter = 3. Hence we can check our algo works.

0 comments:

Post a Comment