Pythonで解く最大積部分配列問題【動的計画法の実装例】

問題の概要

整数配列 nums が与えられたとき、配列内の連続する部分配列(少なくとも1つの要素を含む)の中で、積が最大になるものを見つける問題です。

例えば、配列が [2,3,-2,4] の場合、出力は 6 になります。これは連続する部分配列 [2,3] の積 2×3=6 が最大だからです。

解法のアプローチ

この問題は動的計画法(DP)を活用して解くのが効果的です。重要なポイントは、配列に負の数が含まれる可能性があることです。負の数同士を掛け合わせると正の数になるため、それまでの「最小の積」が突然「最大の積」に変わることがあります。

そこで、各インデックスにおいて「その位置で終わる部分配列の最大積」と「最小積」の両方を追跡します。

アルゴリズムの手順

• nums と同じサイズのリスト max_list と min_list を作成し、0で初期化します
• max_list[0] := nums[0]、min_list[0] := nums[0] と設定します
• i を 1 から nums の長さ - 1 まで繰り返します:
  • max_list[i] = max(max_list[i-1]*nums[i], min_list[i-1]*nums[i], nums[i])
  • min_list[i] = min(min_list[i-1]*nums[i], nums[i], max_list[i-1]*nums[i])
• 最後に max_list の最大値を返します

実装例

以下の実装を見ると、処理の流れがより理解しやすくなります。

class Solution(object):
   def maxProduct(self, nums):
      max_list = [0] * len(nums)
      min_list = [0] * len(nums)
      max_list[0] = nums[0]
      min_list[0] = nums[0]
      for i in range(1,len(nums)):
         max_list[i] = max(max(max_list[i-1]*nums[i],min_list[i-1]*nums[i]),nums[i])
         min_list[i] = min(min(min_list[i-1]*nums[i],nums[i]),max_list[i-1]*nums[i])
      return max(max_list)
ob1 = Solution()
print(ob1.maxProduct([2,3,-2,4,-5,-6,2]))

入力

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

出力

240

実行結果の解説

入力 [2,3,-2,4,-5,-6,2] の場合、部分配列 [4,-5,-6,2] を選ぶと 4×(-5)×(-6)×2 = 240 となり、これが最大の積になります。負の数 -5 と -6 を掛け合わせることで正の値が生まれるため、最大値と最小値の両方を追跡するこの手法が有効に機能していることがわかります。

計算量

時間計算量は O(n)、空間計算量も O(n) です。配列を一度走査するだけで済み、max_list と min_list に各位置での状態を保存するためです。