思路

很明显，为了使 $a_{i-1} < a_i < a_{i+1}$ 那这串花的高度必须是一高一低或一低一高的，那我们定义 $f_{i,0}$ 为当前为上升形势最长花序列的长度，$f_{i,1}$ 当前为下降形势最长花序列的长度。

转移方程

$f_{i,0} = \begin{cases} f_{i-1,1}+1 & a_{i-1} < a_i \\ f_{i-1,0} & a_{i-1} \ge a_i \\ \end{cases}$
$f_{i,1} = \begin{cases} f_{i-1,0}+1 & a_{i-1} > a_i \\ f_{i-1,1} & a_{i-1} \le a_i \\ \end{cases}$

代码

#include<bits/stdc++.h>
using namespace std;
int a[100005],f[100005][2];
int main(){
	int n;
	cin>>n;
	f[1][0]=f[1][1]=1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(i!=1){
			f[i][0]=f[i-1][0];
			f[i][1]=f[i-1][1];	
		}	
		if(a[i-1]<a[i]){
			f[i][0]=f[i-1][1]+1;
		}else if(a[i-1]>a[i]){
			f[i][1]=f[i-1][0]+1;
		}
//		cout<<f[i][0]<<' '<<f[i][1]<<endl;
	}
	cout<<max(f[n][0],f[n][1]);
	return 0;
}