题解：P15705 [2018 KAIST RUN Spring] Zigzag

· · 题解

题目传送门

直接统计所有三个连续的单调元素（简记为“三连”）的位置，我们的最长子段不能包含其中任意一个，所以直接“掐掉”左边一个“三连”的第一个元素和右边这一个“三连”的最后一个元素。然后枚举所有三连，计算它和后一个三连的答案，取最大值即可。

警示后人：别忘了特判没有三连的情况，也别忘了统计最大值时别忘记从开头到第一个三连、从结尾到最后一个三连的情况！

AC Code

#include<bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 5e3+5;
int n, cnt, ed[N], ans;
LL a[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        if(i >= 3 && ((a[i] >= a[i-1] && a[i-1] >= a[i-2]) || (a[i] <= a[i-1] && a[i-1] <= a[i-2])))ed[++cnt] = i;
    }
    if(cnt == 0)ans = n;
    else ans = max(ed[1]-1, n-(ed[cnt]-1)+1);
    for(int i = 1; i < cnt; i++)ans = max(ans, (ed[i+1]-1)-(ed[i]-1)+1);
    printf("%d\n", ans);

    return 0;
}