题解：P15705 [2018 KAIST RUN Spring] Zigzag

BDFZzengboxuan · 2026-03-11 17:57:17 · 题解

显然，当 n<3 的时候，最长子段为 n。

当 n\ge 3 的时候，定义一个变量 now 来记录当前的长度，并用变量 mx 来记录最大值。
对每一个 i>2 的 A_i，如果它与前面构成“Zigzag”序列，则长度加一，否则，当前的最长长度变成 2。每次判断完后要更新 mx。

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