Codeforces Round #605 (Div. 3)：D. Remove One Element【思維+DP？】

Discription

You are given an array a consisting of n integers.

You can remove at most one element from this array. Thus, the final length of the array is n−1 or n.D

Your task is to calculate the maximum possible length of the strictly increasing contiguous subarray of the remaining array.

Recall that the contiguous subarray a with indices from l to r is a[l…r]=al,al+1,…,ar. The subarray a[l…r] is called strictly increasing if al<al+1<⋯<ar.

Input

The first line of the input contains one integer n (2≤n≤2⋅105) — the number of elements in a.

The second line of the input contains n integers a1,a2,…,an (1≤ai≤109), where ai is the i-th element of a.

Output

Print one integer — the maximum possible length of the strictly increasing contiguous subarray of the array a after removing at most one element.

Examples

input

5
1 2 5 3 4
           

output

input

2
1 2
           

output

input

7
6 5 4 3 2 4 3
           

output

Note

In the first example, you can delete a3=5. Then the resulting array will be equal to [1,2,3,4] and the length of its largest increasing subarray will be equal to 4.

題意

給定一串數字，最多可以從這串數字中删除1個數字，問删除後最長的嚴格單調遞增連續子串多長

思路

感覺這道題有點DP的思想，但是可以不用DP做，我就是直接模拟處理，分類讨論的。

先預處理這串數字，将這串數字分成多個連續的嚴格單調遞增子串。用結構體數組

f[]

存儲每一串的起止位置，分别為

l

和

r

并且儲存最大的長度。

周遊與處理完後的結構體數組。一共有三種情況。

1.第

i

個子串和第

i+1

個子串中間差一個，并且

a[f[i+1].l]>a[f[i].r]

，此時最大值為

max(maxx,f[i+1].r-f[i+1].l+2+f[i].r-f[i].l)

2.第i個子串和第i+1個子串相鄰，并且

a[f[i+1].l]>af[i].r-1]&&a[f[i+1].l]<=a[f[i].r]

,此時最大值為

max(maxx,f[i+1].r-f[i+1].l+1+f[i].r-f[i].l)

；

3.第i個子串和第i+1個子串相鄰，并且

a[f[i+1].l+1]>a[f[i].r]&&a[f[i+1].l]<=af[i].r]

，此時最大值為：

max(maxx,f[i+1].r-f[i+1].l+1+f[i].r-f[i].l)

AC代碼

#include<bits/stdc++.h>
using namespace std;
int n;
int a[200010],maxx;
struct node
{
    int l,r;
}f[200010];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int i=1,num=1,flag=0;
    maxx=1;
    while(i<n)
    {
        int tmp=i+1;
        while(a[tmp-1]<a[tmp])
        {
            f[num].l=i;
            f[num].r=tmp;
            tmp++;
            flag=1;
        }
        i=tmp;
        if(flag)
        {
            maxx=max(maxx,f[num].r-f[num].l+1);
            num++;
        }
        flag=0;
        //cout<<f[num-1].l<<" "<<f[num-1].r<<endl;
        //cout<<num<<endl;
        //cout<<maxx<<endl;
    }
    for(int i=1;i<num-1;i++)
    {
        int tmp1=f[i].r;
        int tmp2=f[i+1].l;
        if(a[tmp2]>a[tmp1]&&f[i+1].l-f[i].r<=2)
            maxx=max(maxx,f[i+1].r-f[i+1].l+2+f[i].r-f[i].l);
        else if(a[tmp2]>a[tmp1-1]&&a[tmp2]<=a[tmp1]&&tmp2-tmp1==1)
            maxx=max(maxx,f[i+1].r-f[i+1].l+1+f[i].r-f[i].l);
        else if(a[tmp2+1]>a[tmp1]&&a[tmp2]<=a[tmp1]&&tmp2-tmp1==1)
            maxx=max(maxx,f[i+1].r-f[i+1].l+1+f[i].r-f[i].l);
    }
    cout<<maxx<<endl;
    return 0;
}