Pythonで最大の合計を持つ連続サブリスト（部分配列）の合計を求めるプログラム

配列 A が与えられたとき、「最大の合計を持つ連続した部分リスト（サブアレイ）」を見つけ、その合計値を返すことを考えます。

例えば、配列が A = [-2, 1, -3, 4, -1, 2, 1, -5, 4] の場合、答えは合計 6 となり、該当する部分配列は [4, -1, 2, 1] です。

解き方：動的計画法（DP）の活用

この問題は、動的計画法（Dynamic Programming）を使うことで効率的に解けます。基本的な考え方は、「各位置で終わる部分配列の合計の最大値」を順番に求めていくというものです。

• 配列 A と同じサイズの配列 dp を用意し、すべて 0 で初期化する
• dp[0] := A[0] とする
• i を 1 から A のサイズ − 1 まで繰り返す
  • dp[i] := max(dp[i−1] + A[i], A[i])
• 最後に dp 内の最大値を返す

ここで dp[i] は「i 番目の要素で終わる連続部分配列の合計の最大値」を表します。直前までの累積合計 dp[i−1] に現在の要素 A[i] を足し続けるのが得か、それとも A[i] から新しくスタートし直すのが得かを毎回比較することで、マイナスの合計を引きずらずに済みます。

実装例

class Solution(object):
    def solve(self, nums):
        dp = [0 for i in range(len(nums))]
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-1] + nums[i], nums[i])
        return max(dp)

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

入力

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

出力

8

この例では、[7, -2, 2, 1] という部分配列の合計が 8 となり、これが最大値になります。

計算量と補足

このアルゴリズムの時間計算量は O(n) で、dp 配列の分だけ O(n) の追加メモリが必要です。なお、dp 配列を使わずに「現在の合計」と「最大合計」の 2 つの変数だけで状態を管理すれば、追加メモリを O(1) に抑えることも可能です。この手法は一般に「カダネのアルゴリズム（Kadane's Algorithm）」として知られています。