最长高地

佚名 5年前 (2019-04-20) 随笔 1033人围观抢沙发百度已收录

2509 最长高地

2 秒
262,144 KB
10 分
2 级题

小b有一个长度为n的数组A。

小b认为，如果A的一个区间[l,r]满足r-l>=2，且存在l<p<r使得A[l]<A[l+1]<... <A[p]>A[p+1]>...>A[r]，则[l,r]为一个高地。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

求A中的最长高地的长度。

收起

输入

第一行输入一个非负整数n，表示A数组长度；
第二行输入n个数，表示A数组的元素，以空格隔开；
其中0≤n≤10000，A中任意元素A[i]满足0≤A[i]≤10000.

输出

输出一个数，表示最长高地的长度

输入样例

7
2 1 4 7 3 2 5

输出样例

5
思路：吧每一个点当作最高峰，枚举得到最大
注意：必须中间大两边小所n为1或者2答案都是0

#include<Iostream>
using namespace std;
int f[10005],ff[10005];
int a[10005];
int main(){
    int n;
    cin>>n;
    if(n==1||n==2){
        cout<<0<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++)
    cin>>a[i];
    int sum=1;
    f[1]=1;
    for(int i=2;i<=n;i++){
        if(a[i]>a[i-1])
        f[i]=f[i-1]+1;
        else
        f[i]=1;
    }
    ff[n]=1;
    for(int i=n-1;i>=1;i--){
        if(a[i]>a[i+1])
        ff[i]=ff[i+1]+1;
        else
        ff[i]=1;
    }
    for(int i=1;i<=n;i++){
        if(f[i]+ff[i]-1>sum&&f[i]!=1&&ff[i]!=1)
        sum=f[i]+ff[i]-1;
    }
    cout<<sum<<endl;
    return 0;
}