题目描述
一个整数序列的子序列是指从给定序列中随意地(不一定连续)去掉若干个整数(可能一个也不去掉)后所形成的整数序列。
对于一个整数序列 x1,x2,…,xn
,如果满足下列两个条件之一:
∀i∈[1,n−1],当 i%2==1 时,xi−xi+1为正,当 i%2==0 时,xi−xi+1为负。
∀i∈[1,n−1],当 i%2==1 时,xi−xi+1为负,当 i%2==0时,xi−xi+1为正。
那么,我们就称这个整数序列为 ZigZag 序列。换句话说,ZigZag序列就是一个序列内元素在增大和减小之间不断切换的序列。
例如 1,7,4,9,2,5就是一个 ZigZag 序列。
现在,给定一个长度为 n的整数序列,请你求出它的最长 ZigZag 子序列的长度。
输入格式
第一行包含整数 n。
第二行包含 n个整数。
输出格式
输出一个整数,表示最长 ZigZag 子序列的长度。
数据范围
1≤n≤50,序列内元素取值范围 [1,1000]。
样例
输入样例:
6
1 7 4 9 2 5
输出样例:
6
第一次写题解 233。这道题的想法主要是dp数组动态求解。dp[i]表示到数组第i个元素时的
最大字符串长度。根据题目,这个子序列要求是要序列中的数要一大一小的顺序。那么就定
义一个数组来存储一下个所需元素的要求。之后利用这个来进行判断,如果当前数组的数符
合要求,就使长度加1。之后再与前面符合的条件的数进行比较,取最大值。
C++ 代码
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
int a[51];
int dp[51];
int dpf[51];
bool is_correct(int i,int pre){
if(dpf[pre]){
if(a[i]>a[pre]){
dpf[i]=0;
return true;
}
}else{
if(a[i][HTML_REMOVED]1&&!is_correct(i,flag)) flag–;
return flag;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i) cin>>a[i];
dp[1]=1;
dpf[1]=0;
bool s=true;
for(int i=2;i<=n;i){
if(is_correct(i,i-1)){
dp[i]=dp[i-1]+1;
}
dp[i]=max(dp[find(i)]+1,dp[i]);
if(a[find(i)]==a[i]) dp[i]–;
}
cout<<dp[n];
return 0;
}