题意

给定一个长度为 $n$ 的数组 $a$，我们需要找到最长的连续子序列，使得该子序列在删除至多一个元素后，可以变成一个严格递增的序列。换句话说，就是允许在子序列中跳过最多一个元素，使得剩下的部分严格递增。

思路

我们可以分别计算每个位置 $i$ 向左和向右能延伸的最长严格递增连续段的长度：

• 定义 $l_i$ 为以 $a_i$ 结尾的最长严格递增连续段的长度，即满足 $a_{i - l_i + 1} < a_{i - l_i + 2} < \dots < a_i$，并且 $l_i$ 是最大的。
• 定义 $r_i$ 为以 $a_i$ 开头的最长严格递增连续段的长度，即满足 $a_i < a_{i+1} < \dots < a_{i + r_i - 1}$，并且 $r_i$ 是最大的。

然后，我们考虑删除一个元素 $a_i$ 的情况。如果删除 $a_i$ 后，它左边的连续段和右边的连续段可以拼接成一个更长的递增序列，那么拼接的条件是：

此时，拼接后的长度为：

即：

我们遍历所有可能的 $i$，更新答案的最大值。

算法步骤

1. 初始化数组 $l$ 和 $r$，长度均为 $n$。
2. 从左到右遍历 $i$ 从 $1$ 到 $n$：
   • 如果 $i = 1$ 或 $a_i \le a_{i-1}$，则 $l_i = 1$；
   • 否则 $l_i = l_{i-1} + 1$。
3. 从右到左遍历 $i$ 从 $n$ 到 $1$：
   • 如果 $i = n$ 或 $a_i \ge a_{i+1}$，则 $r_i = 1$；
   • 否则 $r_i = r_{i+1} + 1$。
4. 初始化答案 $ans = 1$（至少可以保留一个元素）。
5. 遍历 $i$ 从 $1$ 到 $n$：
   • 如果 $i > 1$，更新 $ans = \max(ans, l_{i-1} + 1)$（删除 $a_i$ 后只保留左边部分）。
   • 如果 $i < n$，更新 $ans = \max(ans, r_{i+1} + 1)$（删除 $a_i$ 后只保留右边部分）。
   • 如果 $i > 1$ 且 $i < n$ 且 $a_{i-1} + 1 < a_{i+1}$，更新 $ans = \max(ans, l_{i-1} + r_{i+1})$。
6. 输出 $ans$。

复杂度分析

• 时间复杂度：$O(n)$，只需遍历数组常数次。
• 空间复杂度：$O(n)$，用于存储 $l$ 和 $r$ 数组。

代码说明

代码实现时，先计算 $l$ 和 $r$ 数组，然后遍历每个位置 $i$，考虑删除 $a_i$ 或不删除的情况，更新最大长度。注意边界条件的处理，例如 $i=1$ 或 $i=n$ 时只能考虑单侧延伸。

#include<cstdio>
#include<iostream>
using namespace std;
const int Maxn=100000+10;
int a[Maxn],l[Maxn],r[Maxn];
int n,ans;
int main()
{
//	freopen("in.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	scanf("%d",a+i);
	l[1]=r[n]=1;
	for(int i=2;i<=n;++i) // 计算 l[i],r[i]
	if(a[i-1]<a[i])l[i]=l[i-1]+1;
	else l[i]=1;
	for(int i=n-1;i;--i)
	if(a[i]<a[i+1])r[i]=r[i+1]+1;
	else r[i]=1;
	for(int i=1;i<=n;++i) // 这里的边界写的跟上面描述的不一样，其实没区别
	{
		ans=max(ans,l[i-1]+1);
		ans=max(ans,1+r[i+1]);
		if(a[i-1]+1<a[i+1])
		ans=max(ans,l[i-1]+1+r[i+1]); // 求出答案
	}
	printf("%d\n",ans);
	return 0;
}