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 numbers 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
 

using System;

using System.Collections.Generic;

using System.Collections;

using System.Linq;

using System.Text;

 

namespace ConsoleApplication2

{

    class Program

    {

        static void Main(string[] args)

        {

            int[] sequence = { 1, 1, 2, 2, 1, 1, 2, 2 };

            int order = 0, count = 0, temp = 0;

            for (int i = 0; i < sequence.Length – 1; i++)

            {

                if (order == 0)

                {

                    if (sequence[i] > sequence[i + 1])

                    {

                        //decreasing

                        order = -1;

                        temp = sequence[i + 1];

                        count += 2;

                    }

                    if (sequence[i] < sequence[i + 1])

                    {

                        //increasing

                        order = 1;

                        temp = sequence[i + 1];

                        count += 2;

                    }

                }

                else if (order == 1)

                {

                    //Last was increasing, check for decreasing

                    if (temp > sequence[i + 1])

                    {

                        order = -1;

                        count++;

                    }

                    temp = sequence[i + 1];

                }

                else

                {

                    //Last was decreasing, check for increasing

                    if (temp < sequence[i + 1])

                    {

                        order = 1;

                        count++;

                    }

                    temp = sequence[i + 1];

                }

            }

            Console.WriteLine("Length of the longest sequence: " + count);

        }

    }

}

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s