时间复杂度

$O(n)$

参考文献

https://www.acwing.com/solution/content/15094/

C++ 代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    int n;
    cin>>n;

    vector<int> a(n+1);
    a[0]=0;//a[0]不考虑
    for(int i=1;i<=n;++i)//a[1]表示第1个元素
        cin>>a[i];

    vector<int> dp1(n+1);//dp1[i]表示第i个元素结尾的单调上升子串的最大长度
    dp1[0]=0;
    dp1[1]=1;
    for(int i=2;i<=n;++i)
    {
        if(a[i]>a[i-1]) 
            dp1[i]=dp1[i-1]+1;
        else
            dp1[i]=1;
    }

    vector<int> dp2(n+1);//dp1[i]表示第i个元素开头的单调上升子串的最大长度
    dp2[n]=1;
    for(int i=n-1;i>=2;--i)
    {
        if(a[i]<a[i+1]) 
            dp2[i]=dp2[i+1]+1;
        else
            dp2[i]=1;
    }

    int maxLen=dp1[0];//记录最大长度
    //枚举删除一个元素
    for(int i=1;i<=n;++i)
    {
        if(i==1)//删除第一个元素
            maxLen=dp2[i+1];
        else if(i==n)//删除最后一个元素
            maxLen=max(maxLen,dp1[n-1]);
        else if(a[i-1]<a[i+1])//删除中间元素,增大最大长度
            maxLen=max(maxLen, dp1[i-1]+dp2[i+1]);//接起来
        else if(a[i-1]>=a[i+1])//删除这个元素对最大长度没有影响
            maxLen=max(maxLen, max(dp1[i-1],dp2[i+1]));
    }

    cout<<maxLen<<endl;
    return 0;
}