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.
}
else if(foundLocalMinima){
increment the counter to 1.
}

}
```

Lets take the example - 1 4 6 7 6 3 1 2