Given a sequence of integers a

Interview Question

0

of 0 votes

3
Answers
Given a sequence of integers a[1],a[2],...,a[n], we call a sequence b[1], ..., b[m] an alternating sequence if:

for every odd 1 < i <= m, we have b[i] < b[i-1],
for every even 1 < i <= m, we have b[i] > b[i-1].
Given a sequence of integers a[1], ..., a[n], your program must find the length of the longest alternating subsequence. (we define a[i1], ..., a[im] to be a subsequence if 1<=i1< i2<...<im<=n.)

Input

First line of input contains the length of sequence n (1<=n<=200,000). The second line contains n space seperated integers a[1], ..., a[n] (1 <= a[i] <= 10^9).

Output

Output is just a single integer number which denotes the length of longest alternating subsequence.

Sample Input

10

1 2 3 4 5 6 5 4 3 2

Sample Output

3

Explanation: On many alternating subsequences of length three, some are 1 6 2, 3 5 3, 4 6 2 etc. There is no alternating subsequence of length greater than three.

Note : A sequence with just two elements, such that the second element is greater than first is a valid alternating sequence. Moreover a sequence with only one element is also considered an alternating sequence.
- jinalshah2007 April 14, 2012 in United States | Report Duplicate | Flag | PURGE
Algorithm

Email me when people comment.

An error occurred in subscribing you.

Country: United States

More Questions from This Interview

Email me when people comment.

An error occurred in subscribing you.

Comment hidden because of low score. Click to expand.

of 0 vote

stackoverflow.com/questions/6914969/dynamic-programming-find-longest-subsequence-that-is-zig-zag

- Anonymous April 15, 2012 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

int longest_alternating_subsequence(int *arr, int size)
{
    int decreasing=1, i=0, length=0;

   while(i<size-1)
    {

        while(decreasing&&(i<size-1))
        {
            if(arr[i+1]>arr[i])
            {
                decreasing=0;
                length++;
                i++;

            }

            else
                i++;

        }
        while(!decreasing&&(i<size-1))
        {
            if(arr[i+1]<arr[i])
            {
                decreasing=1;
                length++;
                i++;

            }

            else
                i++;

        }
    }

    return length+1;
}

- kubrick April 15, 2012 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

Its just a variation of LIS:

M[i] = Max. alternating seq. till length i

M[i] = max. ( M[x]+1 , if M[x] is odd and arr[i]>arr[x] or if M[x] is even and arr[i]<arr[x]
else
M[x] ) ; 0<=x<i

- deam0n April 16, 2012 | Flag Reply

CareerCup

Interview Question

Books

Videos

Resume Review

Mock Interviews