自动搬运

查看原文

来自洛谷，原作者为

	syzf2222 I am the most handsome man in the world,not one of them

搬运于2025-08-24 22:45:48，当前版本为作者最后更新于2023-03-12 19:32:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

如果修改 $a_i$，最优的修改方案要么是令 $a_i = a_{i+1}-1$，要么是令 $a_i = a_{i-1}+1$。

那么就可以得到一个简单的 $O(n^2)$ 做法，即枚举修改的位置，并计算答案。

预处理出未进行修改时，每个元素作为连续上升子序列的开头与结尾时的最长长度，记为 $f_i,g_i$。

如果存在 $x$ 满足 $a_{i+1}-1\ge x \ge a_{i-1}+1$，那么可以进行合适的修改使得构造出长度为 $g_{i-1}+1+f_{i+1}$ 的答案。

否则只能得到 $g_{i-1}+1$ 或 $f_{i+1}-1$。扫一遍判断即可。复杂度 $O(n)$。