Sunday, August 8, 2010

Sequences



Aadarsh is fond of special type
of sequences which are first increasing then decreasing then increasing then
decreasing and so on or which are first decreasing then increasing then
decreasing and so on like 1,2,1,2,1,2 or 2,1,2,1,2,1 respectively. He wants to
find a longest sub-sequence(not necessarily contiguous) of such nos in a given sequence. Help him out to find
such sequence.

Input Specification


Each test case consists of two
input lines. The first line of a test case contains an integer L,
determining the length of the sequence . The second line of a test case
contains sequence of numbers. L is a positive integer. The sequence contains
integer.

Test Cases are given till end of
file

Output Specification


For each test case output the
Length of the longest sequence which follows the property as mentioned above in
the given input sequence.

Example Input


5
1 2 1 2 1
8
1 2 1 2 2 1 1 4
8
1 2 3 4 5 6 7 8
8
8 7 6 5 4 3 2 1
8
1 1 2 2 1 1 2 2

Example Output


5
6
2
2
4
#include<iostream>
using namespace std;
int main()
{
    int A[100],num;
    while(cin>>num)
    {
        for(int i=0;i<num;i++)
        {
            cin>>A[i];
        }
        int order=0,temp=0,count=0;
        for(int i=0;i<num-1;i++)
        {
            if(order==0)
            {
                if(A[i+1]>A[i])
                {
                     count+=2;
                     order=-1;
                }
                if(A[i+1]<A[i])
                {
                     count+=2;
                     order=1;
                }
                temp=A[i+1];
            }
            else if(order==1)
            {
                if(A[i+1]>temp)
                {
                    count++;
                    order=-1;
                }
                temp=A[i+1];
            }
            else if(order==-1)
            {
                if(A[i+1]<temp)
                {
                    count++;
                    order=1;
                }
                temp=A[i+1];
            }
        }
    cout<<count<<endl;
    }
}

1 comment: