最大平均值問題

Given a[N] 和 M, 找出長度不少於 M 而平均值最大的 continuous subsequence [1]
例如 a = [2, 5, 2, 5], M = 2 最大是 (5+2+5)/3

Algorithm 1

二分答案 d,  問題轉化為
設 b[i] = a[i]-d , 是否存在一段長度至少為 M 的子串而 sum ≥ 0
設 S[i] 為 b[] 的 partial sum array, 再計算 Suffix[i] = max{S[j], j ≥ i}
只要檢查最大的 Suffix[i+M] - S[i] 是否 ≥ 0
之後睇了 [2],  見到一個 linear 的算法

Algorithm 2

如果定義 s[i] = a[1] + a[2] + ... + a[i], 問題轉為搵 max {(s[y]-s[x]) / (y-x), y - x ≥ M}
將 (i, s[i]) 視為 2D plane 上的點, 等價於求 maximum slope

對於每個 y , 要考慮 p[0, y-M] 的點, 更進一步, 其實只要考慮 p[0, y-m] 形成的 lower hull 就足夠
所以要 maintain 著 lower hull (用一個 stack, 反角形成時便 pop)

直覺是類似 tangent 的連到 lower hull 上, 找 tangent point 可以用 binary search
也可以利用 lower hull 的 slope 是 monotonic increasing 這個性質
如果在 lower hull 上 p[y] 是對於 p[x] 的切點, 對於 x' > x, y' < y, 這個組合不會好過 (x, y)

所以只要記住當前的切點, 每次只向右移, 一共是 O(N)

References:
[1] POJ 2018 Best Cow Fences
[2] 周源 <浅谈数形结合思想>