首页 > 代码库 > Codeforces Round #FF (Div. 2) C - DZY Loves Sequences （DP）

Codeforces Round #FF (Div. 2) C - DZY Loves Sequences （DP）

2024-07-22 20:24:08   212人阅读

DZY has a sequence a, consisting of n integers.

We‘ll call a sequence ai,?ai?+?1,?...,?aj(1?≤?i?≤?j?≤?n) a subsegment of the sequencea. The value (j?-?i?+?1) denotes the length of the subsegment.

Your task is to find the longest subsegment of a, such that it is possible to change at most one number (change one number to any integer you want) from the subsegment to make the subsegment strictly increasing.

You only need to output the length of the subsegment you find.

Input

The first line contains integer n (1?≤?n?≤?105). The next line containsn integers a1,?a2,?...,?an (1?≤?ai?≤?109).

Output

In a single line print the answer to the problem — the maximum length of the required subsegment.

Sample test(s)
Input
67 2 3 1 5 6
Output
5
Note

You can choose subsegment a2,?a3,?a4,?a5,?a6 and change its 3rd element (that is a4) to 4.


题意： 寻找长度最大的连续子串满足 子串严格单调递增，前提是你可以修改其中的一个数，把它变成一个任意的数，并且只能修改一次。


可以考虑将 已每个数作为一个连续的串的最后一个元素，那么a[i]就为该串的最大值，找到往前能扩展出的个数，保存在l[i]，往右也是类似。

预处理完成之后考虑第i个位置，如果a[+1] - a[i-1] >１，就可以修改ｉ这个位置，（当然也可以不修改，修改或不修改要看是否ａ［ｉ－１］＜ａ［ｉ］＜ａ［ｉ＋１］）．

那么更新答案ｌ［ｉ－１］＋ｒ［ｉ＋１］＋１．　否则可以修改ｉ这个位置，但前后两段是连不起来的，那么只能更新答案　ｍａｘ（ｌ［ｉ－１］，ｒ［ｉ＋１］）＋１　。


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <cmath>
#define mem(f) memset(f,0,sizeof(f))
#define M 100005
#define mod 10000007
#define MAX 0X7FFFFFFF
#define maxn 500050
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
using namespace std;
typedef long long LL;

int n, a[maxn], l[maxn], r[maxn];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    l[1] = 1;
    for(int i = 2; i <= n; i++)
        if(a[i] > a[i-1]) l[i] = l[i-1] + 1;
        else l[i] = 1;

    r[n] = 1;
    for(int i = n-1; i > 0; i--)
        if(a[i+1] > a[i]) r[i] = r[i+1] + 1;
        else r[i] = 1;

    int ans = r[2] + 1;
    ans = max(ans, l[n-1] + 1);
    for(int i = 2; i < n; i++)
        if(a[i+1] - a[i-1] > 1) ans = max(ans, l[i-1] + r[i+1] + 1);
        else ans = max(ans, max(r[i+1], l[i-1])+1);

    cout << ans << endl;
    return 0;
}



Codeforces Round #FF (Div. 2) C - DZY Loves Sequences （DP）


联系
我们