波动序列_牛客博客

波动序列

时间限制: 1 Sec 内存限制: 128 MB
</center>

题目描述

定义一个序列为波动序列。对于序列A: a1,a2,a3......an, 当且仅当满足a1<a2>a3<a4>a5<a6.......或a1>a2<a3>a4<a5>a6...... 的时候我们说A是一个波动序列。现在给出一个整数序列S,找出S中一段连续子序列K,使得K是一个波动序列，求K最大的长度是多少。

输入

多组输入。

对于每组输入，第一行输入一个整数N(N<=5000),表示序列S的长度。第二行输入N个整数。

输出

对于每组数据，输出一行，一个整数表示答案。

样例输入

样例输出

2
5
1

提示

对于样例1,最长的波动序列有四个，分别是 "12","23","34","45",长度都是2。

对于只含有一个元素的序列也看做是波动序列。

解题思路

令f[i][0]表示以第i个元素结尾且第i个元素小于前一个元素的最长波动序列的长度。

f[i][1]表示以第i个元素结尾且第i个元素大于前一个元素的最长波动序列的长度。

初始化f[i][0]=f[i][1]=1,有 f[i][0]=f[i-1][1]+1 （if(a[i]<a[i-1])）

f[i][1]=f[i-1][0]+1 （if(a[i]>a[i-1])）

答案取最大值。

#include <stdio.h>
#include <algorithm>
using namespace std;
int a[5010], f[5010][2];
int main() {
    int n, i, maxn;
    while (~scanf("%d", &n)) {
        for (i = 0; i < n; i++)
            scanf("%d", &a[i]);
        f[0][0] = f[0][1] = 1;
        maxn = 1;
        for (i = 1; i < n; i++) {
            f[i][0] = f[i][1] = 1;
            if (a[i] < a[i-1])
                f[i][0] = f[i - 1][1] + 1;
            if (a[i] > a[i-1])
                f[i][1] = f[i - 1][0] + 1;
            maxn = max(f[i][0], maxn);
            maxn = max(f[i][1], maxn);
        }
        printf("%d\n", maxn);
    }
    return 0;
}