最大平均值区段

What · 是什么

最大平均值区段问题：给数组 a[1..n] 与下界 L，求长度不小于 L 的连续子段使平均值最大。经典解法：二分答案 x，把判定转化为检查是否存在长度≥L 且 sum-a*x 非负的子段(即 max subarray sum 限制长度)。等价于分数规划(最大化 sum(A)/len(A) 的约束版)。可用前缀和+单调队列 O(n) 判定，二分后总复杂度 O(n log precision)。

Why · 为什么

How · 实现

伪代码

# 二分答案求最大平均值(长度>=L)
lo, hi = min(a), max(a)
for _ in range(60):
  mid = (lo + hi) / 2
  if feasible(mid): lo = mid
  else: hi = mid
return lo

def feasible(x):
  pref[0] = 0
  for i in 1..n: pref[i] = pref[i-1] + a[i] - x
  min_pref = inf
  for r in L..n:
    min_pref = min(min_pref, pref[r - L])
    if pref[r] - min_pref >= 0: return True
  return False

Python 实现

def max_avg_segment(a, L):
    """长度>=L 的最大平均值子段。二分+前缀和判定 O(n log)。"""
    n = len(a)

    def feasible(x):
        pref = 0.0
        # 维护窗口 [0..r-L] 内前缀和最小值
        # 用前缀和数组便于取 pref[r-L]
        pref_list = [0.0] * (n + 1)
        for i in range(n):
            pref_list[i + 1] = pref_list[i] + a[i] - x
        min_pref = float('inf')
        for r in range(L, n + 1):
            # 可用左端点 l 属于 [1, r-L+1], 对应 pref[l-1] 最小
            min_pref = min(min_pref, pref_list[r - L])
            if pref_list[r] - min_pref >= 0:
                return True
        return False

    lo, hi = min(a), max(a)
    for _ in range(60):  # 足够精度
        mid = (lo + hi) / 2.0
        if feasible(mid):
            lo = mid
        else:
            hi = mid
    return lo


def max_avg_segment_brute(a, L):
    """O(n^2) 暴力用于对拍。"""
    best = float('-inf')
    n = len(a)
    for i in range(n):
        s = 0.0
        for j in range(i, n):
            s += a[j]
            if j - i + 1 >= L:
                best = max(best, s / (j - i + 1))
    return best


def max_subarray_sum_kadane(a):
    """Kadane: 最大子段和(不限长度)。"""
    cur = best = a[0]
    for x in a[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best


if __name__ == '__main__':
    import random
    random.seed(3)
    # 确定性样例
    a = [1, 4, 7, 2, 5, 8]
    assert abs(max_avg_segment(a, 2) - 6.5) < 1e-9  # 4+7+2+5+8 = 26/4? 不对
    # 实际最优: 取 [7,2,5,8]=22/4=5.5? 取 [4,7,2,5,8]=26/5=5.2 ... 最优是 [7,2,5,8]=5.5
    # 或 [1,4,7,2,5,8] 全段 27/6=4.5; [4,7]=5.5; [5,8]=6.5 -> 最优 [5,8]=6.5
    assert abs(max_avg_segment(a, 2) - 6.5) < 1e-9
    assert abs(max_avg_segment_brute(a, 2) - 6.5) < 1e-9

    assert max_subarray_sum_kadane([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
    assert max_subarray_sum_kadane([5, 4, -1, 7, 8]) == 23

    # 对拍
    for _ in range(100):
        n = random.randint(1, 12)
        arr = [random.randint(-10, 10) for _ in range(n)]
        L = random.randint(1, n)
        r1 = max_avg_segment(arr, L)
        r2 = max_avg_segment_brute(arr, L)
        assert abs(r1 - r2) < 1e-6, (arr, L, r1, r2)

    print('max_avg a,L=2 =', max_avg_segment(a, 2))
    print('kadane [-2,1,-3,4,-1,2,1,-5,4] =', max_subarray_sum_kadane([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
    print('random brute-compare (100 cases): OK')
    print('All max-avg-segment tests passed!')

易错点

• 判定函数里长度下限 L 对应窗口内取 pref[r-L], 边界别写成 r-L+1
• 二分 60 轮够精度, 但浮点输出要求精确小数位时按题保留; POJ 2018 要求输出*1000取整
• 子段和减去 x 后可能为负仍可能增大下界, 判定条件写 >=0 而非 >0
• 用浮点二分时 lo/hi 初值取 min/max 元素(而非整个范围), 收敛更快
• max_subarray_sum_kadane 处理全负数组: cur 每步 max(x, cur+x) 保证答案≥最大单元素

例题

信源

• CP-Algorithms✓ https://cp-algorithms.com/others/maximum_average_segment.html
• web✓ http://poj.org/problem?id=2018
• CP-Algorithms✓ https://cp-algorithms.com/others/maximum_average_segment.html