Pythonでサイズkの重複しない3つのサブリストの最大合計を求めるプログラム

問題概要

数値のリスト nums と整数 k が与えられたとき、リストの中からサイズ k の重複しない(オーバーラップしない)3つのサブリストを選び、その合計の最大値を求める問題です。

例えば、nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3]、k = 3 の場合、出力は 27 になります。これは、サブリストとして [2, 2, 2]、[4, 4, 4]、[3, 3, 3] を選択でき、その合計が 6 + 12 + 9 = 27 となるためです。

解法のアプローチ

この問題は、累積和(プレフィックスサム)と前後からの最大値の記録を組み合わせることで、効率的に解くことができます。手順は以下の通りです。

• 累積和の作成: P := [0] とし、リスト A の各要素 x に対して「直前の値 + x」を P の末尾に追加していきます。
• ウィンドウごとの合計を計算: Q[i] = P[i + K] − P[i](i は 0 から len(P) − K まで)として、各開始位置におけるサイズ K の部分配列の合計を求めます。
• prefix の構築: prefix[i] に「インデックス i までの範囲における Q の最大値」を格納します。
• suffix の構築: suffix[i] に「インデックス i 以降の範囲における Q の最大値」を格納します。
• 答えの計算: 中央のサブリストの開始位置 i(K ≤ i ≤ len(Q) − K − 1)について、Q[i] + prefix[i − K] + suffix[i + K] を計算し、その最大値を返します。

この方法では、中央のウィンドウを固定した際に、それより左側・右側で取り得る最良のウィンドウの合計を即座に参照できるため、すべての組み合わせを総当たりする必要がありません。

Pythonでの実装例

以下のコードで実際の動作を確認できます。

class Solution:
    def solve(self, A, K):
        # 累積和の作成
        P = [0]
        for x in A:
            P.append(P[-1] + x)

        # サイズKの各ウィンドウの合計
        Q = [P[i + K] - P[i] for i in range(len(P) - K)]

        # prefix: 左側からの累積最大値 / suffix: 右側からの累積最大値
        prefix = Q[:]
        suffix = Q[:]
        for i in range(len(Q) - 1):
            prefix[i + 1] = max(prefix[i + 1], prefix[i])
            suffix[~(i + 1)] = max(suffix[~(i + 1)], suffix[~i])

        # 中央のウィンドウを固定して左右の最大値と組み合わせる
        return max(Q[i] + prefix[i - K] + suffix[i + K]
                   for i in range(K, len(Q) - K))

ob = Solution()
nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3]
k = 3
print(ob.solve(nums, k))

入力

[2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3], 3

出力

27

計算量について

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) です(n はリストの長さ)。3つの区間の組み合わせを素朴に全探索する O(n³) のアプローチと比べて大幅に高速であり、大きな入力サイズにも対応できます。