Whats wrong in this solution of longest alternate subsequence program

  alternating, c++, subsequence

Whats wrong in this solution of longest alternate subsequence program

sequence {x1, x2, .. xn} is alternating sequence if its elements satisfy one of the following relations :

x1 < x2 > x3 < x4 > x5….. or x1 >x2 < x3 > x4 < x5…..

Your task is to find the longest such sequence.

Input:

The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains an integer N denoting the size array A.

The second line of each test case contains N space separated integers denoting elements of the array A[ ].

Output:

Print the length of the longest alternating subsequence for each testcase in a new line.

Constraints:

1<= T <=100

1<= N <=1000

1<= A[ ] <=1000

Example:

Input:

2

3

1 5 4

8

10 22 9 33 49 50 31 60

Output:

3

6

The idea behind my code is I am creating a dp array with base case as 1. Now the first time the value of given array changes a[i+1]>a[i] or a[i+1] < a[i] I put its value as 2 i.e. (dp[i+1]=2) in dp array.
now suppose if last time its value increases then i will increment value of dp when the next element of given array will decrease then its previous value. and I will repeat this process alternatively.
Now this code seems to me correct but when I am solving it on coding platforms it is giving me wrong output for some test cases. it is giving me more value then the actual answer.
can anyone help me out where am I wrong.

my code is below.

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int batman(int a[],int n,int start)
{
   int dp[n];
   for(int i=0;i<=start;i++)
   {
       dp[i]=1;
   }
    bool check;
    if(a[start+1]>a[start]){ check=true; dp[start+1]=2;}
    else{ dp[1+start]=2; check=false;}
    for(int i=2+start;i<n;i++)
    {
        if(check==true)
        {
            if(a[i]>a[i-1])
            {
                dp[i]=dp[i-1];

            }
            else{
                check=false;
                dp[i]=dp[i-1]+1;
                continue; }
        }
        if(check==false)
        {
            if(a[i]<a[i-1])
            {
                dp[i]=dp[i-1];

            }
            else{
                check=true;
                dp[i]=dp[i-1]+1;
                continue; }
        }
    }
    return dp[n-1];
}
int main()
 {
    int t;cin>>t;
    while(t--)
    {
        //code here
        int n;
        cin>>n;
        int a[n];
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        int i=0;
        while(a[i+1]==a[i])
        {
            i++;
        }
       cout<<batman(a,n,i)<<endl;
    }
    return 0;
}


Source: StackOverflow C++

LEAVE A COMMENT