Pythonで連続する部分配列の最大積を求めるプログラム

nums という配列が与えられたとき、少なくとも1つの要素を含む「連続した部分配列」の中から、要素の積が最大になるものを見つけて、その積を返すことを考えます。例えば、配列が [1,9,2,0,2,5] の場合、連続する部分配列 [1,9,2] の積が最大となるため、出力は 18 になります。

解法のアプローチ

この問題は動的計画法（DP）を使って効率的に解くことができます。ポイントは、負の数同士を掛けると正の数になる可能性があるため、各位置における「最大積」と「最小積」の両方を追跡することです。

具体的な手順は以下の通りです。

• max_list：nums と同じサイズのリストを作成し、0で初期化する
• min_list：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 の最大値を返す

この方法では、時間計算量・空間計算量ともに O(n) で問題を解くことができます。

実装例

以下のコードで、より理解を深めましょう。

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([1,9,2,0,2,5]))

入力

[1,9,2,0,2,5]

出力

18