牛牛的数列

题目链接：牛牛的数列

好久没写代码，一道简单dp都做了好久。

思路：从左往右算每个位置的最长连续上升子序列，从右往左算每个位置的最长连续下降子序列。然后遍历数组，对一个不满足要求的数，如果能修改成功（修改完后，该数大于其左边的数，小于其右边的数），那么修改后形成的长度就等于1+右边的最长连续下降子序列长度+左边的最长连续上升子序列长度；如果不能修改成功（卡了好久我才反应过来，还有这种情况），那么修改后形成的长度就等于1+max(左边的最长连续上升子序列长度，右边的最长连续下降子序列长度）。

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005];
int b[100005];
int c[100005];
int main(){
    cin>>n;
    int i;
    for(i=1;i<=n;i++)
        cin>>a[i];
    a[n+1]=1000000005;
    b[1]=1;
    int maxn=0;
    c[n]=1;
    for(i=2;i<=n;i++)
    {
        if(a[i]>a[i-1])
            b[i]=b[i-1]+1;
        else
            b[i]=1;
    }
    for(i=1;i<=n;i++)
    {
        if(b[i]>maxn)
            maxn=b[i];
    }
    for(i=n-1;i>=1;i--)
    {
        if(a[i]<a[i+1])
            c[i]=c[i+1]+1;
        else
            c[i]=1;
    }
    for(i=1;i<=n;i++)
    {   
        int len=0;
        if(a[i]>=a[i+1]||a[i]<=a[i-1])
        {
            if(a[i-1]+1<a[i+1])
                len=b[i-1]+c[i+1]+1;
            else
                len=max(1+b[i-1],c[i+1]+1);

            if(len>maxn)
                maxn=len;
        }
    }
    cout<<maxn<<endl;
}