Pythonで長さk以上のサブリストの最大平均値を求める方法

数値のリスト nums と整数 k が与えられたとき、長さが k 以上である任意の連続するサブリスト（部分配列）の中から、平均値が最大となるものを求める問題を考えます。

例えば、入力が nums = [2, 10, -50, 4, 6, 6]、k = 3 の場合を考えてみましょう。このとき出力は 5.33333333 になります。これは、サブリスト [4, 6, 6] の平均値 (4 + 6 + 6) ÷ 3 ≒ 5.333 が、条件を満たすすべての候補の中で最も大きいためです。

解法のアプローチ：二分探索とスライディングウィンドウ

この問題は、平均値の候補範囲に対して二分探索（バイナリサーチ）を適用しながら、各ステップでスライディングウィンドウの要領で合計値を更新していくことで、効率的に解くことができます。すべてのサブリストを列挙する素朴な方法に比べ、計算量を大幅に抑えられるのがポイントです。

アルゴリズムの手順

• left := nums の最小値、right := nums の最大値 とします。
• s := nums のインデックス 0 から k − 1 までの要素の合計
• largest_avg := s / k
• left <= right の間、以下を繰り返します。
  • mid := (left + right) / 2 の整数部分
  • sum1 := s、avg := s / k、sum2 := 0、cnt := 0 で初期化
  • i を k から nums のサイズ − 1 まで繰り返します。
    • sum1 := sum1 + nums[i]
    • sum2 := sum2 + nums[i − k]
    • cnt := cnt + 1
    • avg := avg と (sum1 / (cnt + k)) の大きい方
    • もし sum2 / cnt <= mid ならば
      • sum1 := sum1 − sum2
      • cnt := 0、sum2 := 0
    • avg := avg と (sum1 / (cnt + k)) の大きい方
  • largest_avg := largest_avg と avg の大きい方
  • もし avg > mid ならば left := mid + 1、そうでなければ right := mid − 1
• largest_avg を返します。

Pythonでの実装例

それでは、理解を深めるために実際のコードを見てみましょう。

class Solution:
   def solve(self, nums, k):
      left, right = min(nums), max(nums)
      s = sum(nums[:k])
      largest_avg = s / k
      while left <= right:
         mid = (left + right) // 2
         sum1 = s
         avg = s / k
         sum2 = 0
         cnt = 0
         for i in range(k, len(nums)):
            sum1 += nums[i]
            sum2 += nums[i - k]
            cnt += 1
            avg = max(avg, sum1 / (cnt + k))
            if sum2 / cnt <= mid:
               sum1 -= sum2
               cnt = 0
               sum2 = 0
            avg = max(avg, sum1 / (cnt + k))
         largest_avg = max(largest_avg, avg)
         if avg > mid:
            left = mid + 1
         else:
            right = mid - 1
      return largest_avg
ob = Solution()
nums = [2, 10, -50, 4, 6, 6]
k = 3
print(ob.solve(nums, k))

入力

[2, 10, -50, 4, 6, 6], k = 3

出力

5.333333333333333

まとめ

このアルゴリズムは、取り得る平均値の範囲［リストの最小値，最大値］に対して二分探索を繰り返すことで、目的の最大平均値へと絞り込んでいきます。窓の合計を都度リセットしながら走査するため、全サブリストを総当たりする O(n²) の手法よりも高速に動作し、要素数の多いリストでも実用的な時間内に処理できるのが魅力です。