Pythonで循環リストの最大部分配列合計を求めるプログラム

数値のリスト nums が与えられたとします。ここで、nums の先頭と末尾が隣り合っている「循環リスト」を考えます。このとき、循環リスト内の空でない部分リスト（部分配列）の中から、合計が最大になるものを見つける必要があります。

例として、入力が nums = [2, 3, -7, 4, 5] の場合を考えてみましょう。この場合の出力は 14 になります。部分リスト [4, 5, 2, 3] を選ぶと、その合計は 14 になるからです。

解法のアプローチ

この問題は、有名なKadaneのアルゴリズムを応用することで効率的に解けます。ポイントは、答えとなる部分配列が2通りの場合に分けられることです。

• ケース1：循環をまたがない場合 — 通常のKadaneのアルゴリズムで最大合計 max_sum を求めます。
• ケース2：循環をまたぐ場合 — この場合の合計は「全体の合計 − 最小部分配列の合計」と等しくなります。つまり、合計が最小の部分配列を除外した残りの部分が答えになります。

最終的な答えは、この2つの値のうち大きい方です。ただし、すべての要素が負の場合は注意が必要です。この場合は循環をまたぐ有効な解が存在しないため、通常のKadaneの結果（max_sum）をそのまま返します。

アルゴリズムの手順

• max_sum := 負の無限大、cur_max := 0 で初期化する
• min_sum := 正の無限大、cur_min := 0 で初期化する
• nums 内の各要素 num に対して以下を繰り返す
  • cur_max := max(num, cur_max + num)
  • max_sum := max(max_sum, cur_max)
  • cur_min := min(num, cur_min + num)
  • min_sum := min(min_sum, cur_min)
• もし max_sum <= 0 なら、max_sum を返す（全要素が負の場合）
• max(max_sum, sum(nums) - min_sum) を返す

それでは、実際の実装を見て理解を深めましょう。

実装例

import math

class Solution:
    def solve(self, nums):
        max_sum = -math.inf
        cur_max = 0
        min_sum = math.inf
        cur_min = 0
        for num in nums:
            cur_max = max(num, cur_max + num)
            max_sum = max(max_sum, cur_max)
            cur_min = min(num, cur_min + num)
            min_sum = min(min_sum, cur_min)
        if max_sum <= 0:
            return max_sum
        return max(max_sum, sum(nums) - min_sum)

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

入力

[2, 3, -7, 4, 5]

出力

14

計算量について

このアルゴリズムはリストを一度だけ走査するため、時間計算量は O(n)、追加の記憶領域も O(1) で済みます。循環配列の問題としては非常に効率的な解法と言えます。