最大積部分配列の問題を解決する方法

ブルートフォース法: 最も単純な方法は、配列内のすべての部分配列の積を計算し、最大値を見つける方法です。これは、2つのループを使用して実装することができます。外側のループは部分配列の開始位置を指定し、内側のループは終了位置を指定します。この方法の時間計算量はO(n^2)です。
動的計画法(Dynamic Programming): 動的計画法を使用すると、部分問題の最適解を計算してメモ化することができます。具体的な手順は以下の通りです。
- 配列の要素を順番に見ていき、現在の要素を含む部分配列の最大積を計算します。
- 現在の要素が正の場合、最大積は前の要素までの最大積に現在の要素を掛けたものです。
- 現在の要素が負の場合、最大積は前の要素までの最小積に現在の要素を掛けたものです。
- 現在の要素が0の場合、最大積は0となります。
- 各ステップで最大積を更新することで、最終的な結果を得ることができます。この方法の時間計算量はO(n)です。

以下に、Pythonでの動的計画法を用いた実装例を示します。

def max_product_subarray(nums):
    max_product = nums[0]
    max_so_far = nums[0]
    min_so_far = nums[0]
    for i in range(1, len(nums)):
        current_num = nums[i]
        if current_num < 0:
            max_so_far, min_so_far = min_so_far, max_so_far

        max_so_far = max(current_num, max_so_far * current_num)
        min_so_far = min(current_num, min_so_far * current_num)
        max_product = max(max_product, max_so_far)
    return max_product
nums = [2, 3, -2, 4, -1, 0, 2, 5, -3]
result = max_product_subarray(nums)
print("Maximum product subarray:", result)

このコードは、与えられた配列 nums の最大積部分配列を計算し、結果を表示します。