题解：P15705 [2018 KAIST RUN Spring] Zigzag
不想说话真君
·
·
题解
考虑递推。
```
#include <bits/stdc++.h>
using namespace std;
int a[10000000];
int dp[10000000];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
if (n <= 2) {
cout << n << endl;
return 0;
}
for(int i = 0;i <= n;i++) dp[i] = 2;
int ans = 2;
for (int i = 2; i < n; ++i) {
if (!(a[i-2] <= a[i-1] && a[i-1] <= a[i]) && !(a[i-2] >= a[i-1] && a[i-1] >= a[i])) {
dp[i] = dp[i-1] + 1;
}
ans = max(ans, dp[i]);
}
cout << ans << endl;
return 0;
}
```