题解

思路

删除位置 $i$ 后，可能跨过它合并的递增区间由两部分组成：以 $i-1$ 结尾的最长严格递增段，以及以 $i+1$ 开头的最长严格递增段。两部分能合并当且仅当 $a_{i-1}<a_{i+1}$。

做法

预处理：

• left[i]：以 $i$ 结尾的最长严格递增连续段长度；
• right[i]：以 $i$ 开头的最长严格递增连续段长度。

先用所有 left[i] 更新不删除时的答案。再枚举内部位置 $i$，若 $a_{i-1}<a_{i+1}$，用 left[i-1]+right[i+1] 更新答案。删除首尾不会优于某个原有递增段，已经包含在初始答案中。

正确性证明

不删除元素时，任何严格递增子区间都以某个位置结尾，其最大长度由对应 left 状态统计。若最优方案删除内部位置 $i$ 且跨过该位置，则删除后区间在左侧只能取以 $i-1$ 结尾的完整递增后缀，在右侧只能取以 $i+1$ 开头的完整递增前缀；两者合法拼接的充要条件是 $a_{i-1}<a_{i+1}$，算法恰好计算其总长。若删除后最优区间不跨被删位置，则它本来就是原数组中的递增段。故算法覆盖所有方案并取到最优值。

复杂度分析

时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

子任务说明

• $n\le20$ 时枚举删除位置与所有区间。
• $n\le3000$ 时枚举删除位置并重新扫描数组。
• 满数据用前后缀递增长度常数时间评估每次删除。