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;
}