ZigZag Sequence Problem Top Coder 03 Semi Finals 3

Level Of the Problem ;-   EASY

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

SOLUTION:

#include<iostream>

#include<vector>

using namespace std;

int main()

{

    int T = 0 ; 

    int N = 0 ;

    cin>>T;

    vector<int>num;

    vector<int> sol;

    vector<int>sign; // USED TO STORE THE SIGN OF LAST TWO ELEMENTS

    for(int t = 0 ; t < T ; t++)

    {

            cin>>N;

            num.clear();

            num.resize(N);

            sol.clear();

            sol.resize(N+1);

            sign.clear();

            sign.resize(N);

            for(int i = 0 ; i < N ; i++)

            {

                    cin>>num[i];

                    sol[i] = 1 ;

                    sign[i] = 0 ;

                    

            }

            sol[N]= 1 ;

            for(int i = 1 ; i < N ; i++)

            {

                    for(int j = 0 ; j < i ; j++)

                    {

                            if( j == 0)

                            {

                                

                                sign[i] = num[i] - num[j]; 

                                sol[i] = sol[j] + 1 ;

                            }

                            else if(  ( (sign[j] > 0) && (num[i] - num[j] < 0))  || ( (sign[j] < 0) && (num[i] - num[j] > 0) ) && ( sol[j] + 1 > sol[i]) )

                            {

                            sol[i] =  sol[j] +  1 ;

                            sign[i] = num[i] - num[j]; 

                                

                            }

                    }

            }  

            cout<<sol[N-1]<<endl;

    }

    cin.get();

    return 0;

}