因为有上下上和下上下两种情况，所以动态规划dp数组开二维

dp[i][0] 代表a[i]在序列当中是由序列的前一个数上升来的

dp[i][1] 代表a[i]在序列当中是由序列的前一个数下降来的

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<string.h>
#include<queue>
#include<math.h>
#include<bits/stdc++.h>
using namespace std;
const int maxv=4010;

int main() {
	int n;
	while(cin>>n)
	{
		int a[n+5];
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
		}
		int dp[n+1][2];
		memset(dp,0,sizeof(dp));
		int ans=1;
		dp[0][0]=1;// 代表是上升
		dp[0][1]=1;
		for(int i=1;i<n;i++)
		{
			for(int j=0;j<i;j++)
			{
				if(a[i]>a[j])
				{
					dp[i][0]=max(dp[i][0],dp[j][1]+1);
				}
				else if(a[i]<a[j])
				{
					dp[i][1]=max(dp[i][1],dp[j][0]+1);
				}
			}
			ans=max(ans,max(dp[i][0],dp[i][1]));
			
		}
		cout<<ans<<endl;
	}
	return 0;
}