题目题解：最大连续子序列平均值（长度至少为$k$）

一、题目解析

给定长度为 $n$ 的整数数组，需找到长度至少为 $k$ 的连续子序列，使得该子序列的平均值最大。

• 直接暴力枚举所有长度≥$k$ 的子序列：时间复杂度为 $O(n^2)$，对于 $n$ 较大（如 $10^5$ 级别）的用例，会因超时无法通过。
• 核心矛盾：需将“找最大平均值”的优化问题，转化为可高效判定的问题，降低时间复杂度。

二、算法思路（二分查找 + 前缀和优化）

1. 核心思想：二分查找转化判定问题

最大平均值的取值范围是数组最小值 ~ 数组最大值（因为子序列平均值不会超出数组元素的取值区间）。利用二分查找逐步缩小这个范围，每次验证“当前候选平均值是否存在对应的合法子序列”。

2. 关键步骤：判定候选平均值是否可行

对于候选平均值 $mid$，需判断：是否存在长度≥$k$ 的连续子序列，其平均值≥$mid$。

• 转化子问题：若子序列 $a[l..r]$（长度 $r-l+1 ≥k$）的平均值≥$mid$，则等价于：
  [ \frac{a[l] + a[l+1] + ... + a[r]}{r-l+1} ≥ mid ]
  两边同乘长度（正数，不改变不等号方向），整理得：
  [ (a[l] - mid) + (a[l+1] - mid) + ... + (a[r] - mid) ≥ 0 ]
  即：构造新数组 $b[i] = a[i] - mid$，问题转化为“是否存在长度≥$k$ 的连续子数组，使得 $b$ 的子数组和≥$0$”。

3. 前缀和优化判定效率

用前缀和数组 $s$ 快速计算 $b$ 的子数组和：

• 前缀和定义：$s[0] = 0$，$s[i] = b[1] + b[2] + ... + b[i]$。
• 子数组 $b[j+1..i]$ 的和 = $s[i] - s[j]$（需满足 $i-j ≥k$，即 $j ≤ i-k$）。

为快速找到“是否存在 $j ≤ i-k$ 使得 $s[i] - s[j] ≥0$”，只需维护前 $i-k$ 个前缀和中的最小值 $min\_prefix$：

• 若 $s[i] - min\_prefix ≥0$：说明存在 $j$ 满足条件，$mid$ 可行。
• 否则：更新 $min\_prefix$（纳入新的前缀和 $s[i-k+1]$，为后续 $i$ 增大做准备）。

三、算法流程总结

1. 初始化二分区间：左边界 $left =$ 数组最小值，右边界 $right =$ 数组最大值。
2. 二分迭代：
   • 计算中间值 $mid = (left + right) / 2$。
   • 调用判定函数，检查 $mid$ 是否可行。
   • 若可行：说明存在更大的平均值，将 $left = mid$（保留右半区间）。
   • 若不可行：说明平均值需更小，将 $right = mid$（保留左半区间）。
3. 终止条件：当 $right - left < EPS$（$EPS$ 为精度阈值，如 $1e-6$），此时 $left$（或 $right$）即为最大平均值。

四、算法分析

• 时间复杂度：$O(n \cdot \log \frac{M}{EPS})$
  • $n$ 为数组长度，每次判定需遍历数组（$O(n)$）。
  • 二分次数由 $M$（数组最大值与最小值的差）和 $EPS$ 决定，通常迭代 $30$~$50$ 次即可满足精度要求。
• 空间复杂度：$O(n)$（存储前缀和数组，可优化为 $O(1)$，仅维护当前前缀和与最小前缀和）。

五、算法标签

• 二分查找
• 前缀和
• 子数组和问题
• 优化判定（转化问题思想）