P6181

LeiZeProMax · 2022-09-13 18:10:03 · 题解

蒟蒻的第一篇题解，如有错误请指出。

题意：给定一个序列的长度 n 和序列中的数，求最长连续单峰子序列。

我们可以定义一个 ans 来代表当前最长单峰子序列的长度，因为 n\le10^5，所以只需要用 int 定义就可以。

求连续单峰子序列的长度也很简单，用每个数之后连续不上升序列终点减去这个数之前连续不下降序列起点再 +1 即可。

注意：当连续单峰子序列的长度等于 n 时，我们可以直接跳出，从而节省一定的时间。

Code

#include<bits/stdc++.h>
#define Max(i,j) (i>j?i:j)
using namespace std;
int i,n,ans=-12,a[100001];
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
    {
        int x=i,y=i;
        //x为连续不下降序列起点，y为连续不上升序列终点 
        for(;a[x-1]<=a[x]&&x>1;x--);
                //求连续不下降序列起点 
        for(;a[y+1]<=a[y]&&y<n;y++);
                //求连续不上升序列终点 
        ans=Max(ans,y-x+1);
        //如果ans小于当前单峰子序列就更改答案(记得+1) 
        if(y-x+1==n)break;
        //如果连续单峰子序列长度与n相同，直接跳出 
    }
    printf("%d",ans);
    return 0;
}