题解2 - 题解 - 青藤 OJ

讨论

题解

花匠

题解2

#include<bits/stdc++.h>

using namespace std;

const int N=2000001;

int a[N];

int dp1[N];

int dp2[N];

int main()

{

int n,sum=1;

cin>>n;

dp1[1]=dp2[1]=1;

for(int i=1;i<=n;i++) cin>>a[i];

for(int i=2;i<=n;i++)

{

	dp1[i]=dp1[i-1];

	dp2[i]=dp2[i-1];

	if(a[i]>a[i-1]) dp1[i]=max(dp1[i],dp2[i-1]+1);

	if(a[i]<a[i-1]) dp2[i]=max(dp2[i],dp1[i-1]+1);

	sum=max(sum,max(dp1[i],dp2[i]));

}

cout<<sum;

return 0;

}