题目描述

难度分:$1600$

输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

你可以修改$a$中的至多一个数（修改成任意整数）。输出$a$的最长严格递增子数组的长度。注：子数组是连续的。

输入样例

6
7 2 3 1 5 6

输出样例

5

算法

前后缀分解

预处理出$pre$和$suf$两个数组，$pre[i]$表示以$a[i]$结尾的最长严格递增子数组长度，$suf[i]$表示以$a[i]$开头的最长严格递增子数组长度。状态转移如下：

1. 如果$a[i] \gt a[i-1]$，那么$pre[i]=pre[i-1]+1$，表示$a[i]$可以接在$a[i-1]$结尾的最长递增子数组后面；否则$pre[i]=1$，表示$a[i]$自成一个严格递增子数组。
2. 同理如果$a[i] \lt a[i+1]$，那么$suf[i]=suf[i+1]+1$，否则$suf[i]=1$。

如果一个数都不修改，那么答案就是$max_{i \in [1,n]}pre[i]$。

否则枚举修改的位置$i$，添加两个哨兵$a[0]=0$，$a[n+1]=2 \times 10^9$。如果要修改$a[i]$，则$a[i-1]+1 \lt a[i+1]$时可以把$a[i]$修改为$(a[i-1]+1,a[i+1])$中的一个数，从而把$a[i-1]$结尾的最长递增子数组和$a[i+1]$开头的最长递增子数组连接起来变成一个长度为$pre[i-1]+suf[i+1]+1$的最长递增子数组。否则就只能将$a[i-1]$结尾的最长递增子数组或$a[i+1]$开头的最长递增子数组加长$1$。

所有$i$位置答案的最大值以及$max_{i \in [1,n]}pre[i]$中较大的那个就是最终答案。

复杂度分析

时间复杂度

$O(n)$遍历可以求出$pre$和$suf$两个数组。遍历修改的位置$i \in [1,n]$，每个位置求答案的时间复杂度为$O(1)$，时间复杂度为$O(n)$。因此，整个算法的时间复杂度为$O(n)$。

空间复杂度

除了输入的$a$数组，空间消耗主要在于$pre$和$suf$两个数组，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int n, a[N], pre[N], suf[N];

int main() {
    scanf("%d", &n);
    int ans = 1;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        pre[i] = a[i] > a[i - 1]? pre[i - 1] + 1: 1;
        ans = max(ans, pre[i]);
    }
    a[n + 1] = 2e9;
    suf[n + 1] = 0;
    for(int i = n; i >= 1; i--) {
        suf[i] = a[i] < a[i + 1]? suf[i + 1] + 1: 1;
    }
    for(int i = 1; i <= n; i++) {
        ans = max(ans, max(pre[i - 1], suf[i + 1]) + 1);
        if(a[i - 1] + 1 < a[i + 1]) {
            ans = max(pre[i - 1] + suf[i + 1] + 1, ans);
        }
    }
    printf("%d\n", ans);
    return 0;
}