sequence {x1, x2, .. xn} является чередующейся последовательностью, если ее элементы удовлетворяют одному из следующих соотношений:
x1 x3 x5 ..... или x1> x2 x4
Ваша задача - найти самую длинную такую последовательность.
Ввод:
Первая строка ввода содержит целое число T обозначает количество тестовых случаев. Затем следуют тесты T. Первая строка каждого теста содержит целое число N, обозначающее массив размеров A.
Вторая строка каждого теста содержит N целых чисел, разделенных пробелом, обозначающих элементы массива A [].
Выходные данные:
Вывести длину самой длинной чередующейся подпоследовательности для каждого тестового примера в новой строке.
Ограничения:
1 <= T <= 100 </p>
1 <= N <= 1000 </p>
1 <= A [] <= 1000 </p>
Пример:
Ввод:
2
3
1 5 4
8
10 22 9 33 49 50 31 60
Выход:
3
6
Идея, лежащая в основе моего кода, заключается в том, что я создаю массив dp с базовым регистром, равным 1. Теперь, когда значение данного массива в первый раз изменяется a[i+1]>a[i] or a[i+1] < a[i] Я ставлю его значение как 2, т. Е. (dp[i+1]=2) в массиве дп. Теперь предположим, что если в последний раз его значение увеличивается, то я буду увеличивать значение dp, когда следующий элемент данного массива будет уменьшаться, тогда как его предыдущее значение. и я повторю этот процесс поочередно. Теперь этот код кажется мне правильным, но когда я решаю его на платформах кодирования, он дает неправильный вывод для некоторых тестовых случаев. это дает мне большую ценность, чем фактический ответ. Может кто-нибудь помочь мне, где я не прав.
мой код ниже.
#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;
}