Pythonでリストをk回連結した配列の最大部分配列の合計を求める方法

問題概要

数値のリスト nums と整数 k が与えられたとします。ここで k は、nums を k 回繰り返して連結した大きなリストを表します。この課題では、その大きなリストの中から「合計が最大となる連続する部分リスト」を見つけ、その合計を求める必要があります。

たとえば、入力が nums = [2, 4, 5, -4]、k = 1 の場合、出力は 11 になります。これは [2, 4, 5] という部分リストを選ぶことで、合計 2 + 4 + 5 = 11 が得られるためです。

解決のためのアプローチ

この問題は、有名な「カダネのアルゴリズム(最大部分配列和)」を応用することで効率的に解けます。リストを実際に k 回連結すると、k が大きい場合にメモリや計算コストが膨大になります。そこで、最大でも2周分だけ走査し、残りの繰り返し分はリスト全体の合計値で補うのがポイントです。

具体的には、以下の手順で処理を進めます。

• s(累積和)、ans(答え)、lo(累積和の最小値)をすべて 0 で初期化します。
• k と 2 のうち小さい方の回数だけ、以下のループを実行します。
  • nums の各要素 x について:
    • s に x を加算します。
    • lo を lo と s の最小値に更新します。
    • ans を ans と s - lo の最大値に更新します。
• 最後に、ans + max(0, sum(nums)) * max(0, k - 2) を返します。

なぜ min(k, 2) 回の走査で十分なのでしょうか。それは、リストの境界をまたいで最大となる区間(循環する区間)まで考慮するために、2周分の走査が必要だからです。さらに、3周目以降の中央部分は必ず「リスト全体の合計」の繰り返しと同じになるため、sum(nums) が正の場合に限り (k - 2) 倍して加算すればよいのです。

実装例(Python)

class Solution:
    def solve(self, nums, k):
        s = ans = lo = 0
        for _ in range(min(k, 2)):
            for x in nums:
                s += x
                lo = min(lo, s)
            ans = max(ans, s - lo)
        return ans + max(0, sum(nums)) * max(0, (k - 2))

ob = Solution()
nums = [2, 4, 5, -4]
k = 1
print(ob.solve(nums, k))

入力

[2, 4, 5, -4], 1

出力

11

まとめ

この手法を使えば、リストを実際に k 回連結することなく、要素数 n に対して O(n × min(k, 2)) の計算量で最大部分配列の合計を求められます。k が非常に大きい場合でも高速に動作する点が大きな魅力です。最大部分配列問題の応用として、ぜひ理解しておきましょう。