Pythonで最大部分配列（Maximum Subarray）問題を解く方法【動的計画法】

最大部分配列問題とは

整数配列 A が与えられたとき、長さが 1 以上の連続する部分配列の中で、要素の合計が最大になるものを見つけ、その合計値を返すことを考えます。

例えば、配列 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 内の最大値を返す

ここでのポイントは、「i 番目の要素で終わる部分配列の最大合計」を dp[i] として記録していく点です。直前までの累積合計がマイナスになる場合は、そこから新しく部分配列を始めた方が得であるため、max() を使って「継続するか、新しく始めるか」を判断しています。

それでは、実際の実装例を見てみましょう。

Pythonでの実装例

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        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])
        # print(dp)
        return max(dp)

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

入力

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) に抑えることも可能です（この手法は一般に「カダネのアルゴリズム」と呼ばれています）。