线性扫描与动态规划

针对此类“最长连续满足某条件的子数组”问题，最经济的算法范式是线性扫描，其本质是动态规划中状态压缩的简化版。

1. 核心思想

我们定义 为以索引 结尾的最长稳定连续子数组的长度。 根据稳定性定义，状态转移方程如下：

  • 若 ，则
  • 若 ，则 （当前元素只能独立构成一个长度为 1 的子数组）

2. 空间优化

由于 的计算仅依赖于 ，我们不需要维护整个 DP 数组。通过引入一个变量 current_length 来实时记录当前的稳定长度，并用 max_length 记录遍历过程中的全局最大值，可将空间复杂度从 降低至 。

复杂度分析

  1. 时间复杂度：

    算法仅需对长度为 的数组进行一次单向遍历。每个元素被访问的次数为常数（1次比较，1次状态更新），完全符合线性时间复杂度要求。

  2. 空间复杂度：

    除了存储输入的原始数据外（如果视为输入流，则不需要存储整组数据），算法仅需维护两个整型变量（当前段长度与全局最长长度），与输入规模 无关。