Maximum Product Subarray

ふつう動的計画法

+10

nums の部分配列の要素をすべて掛け合わせ、部分配列が取り得る最大の積を返します。部分配列は間を空けずに連続する要素を取り、空になることはないため、負の数だけの配列にも答えがあります。0 と負の値も使用できます。

関数

maxProduct(nums: integer-array) → integer

numsinteger-array: 乗算する整数。それぞれ -10 から 10 の範囲
戻り値integer: 空でない部分配列の最大積

制約

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
すべての部分配列の積は、32ビット符号付き整数に収まります。

例

入力: nums = [2, -5, 3, -2, 0, 4]
出力: 60
説明: 2つの負の数は打ち消し合います。2 × -5 × 3 × -2 = 60。0が配列を2つに分け、反対側の4は60を上回れません。

入力: nums = [-2, 3, -4, -1]
出力: 24
説明: 配列全体の積は、負の数が3つ含まれているため -24 です。最後の要素を除くと、負の数が2つ残ります。-2 × 3 × -4 = 24となり、最初の要素を除いたときに得られる12を上回ります。

入力: nums = [-6, 0, -7]
出力: 0
説明: 0を避ける部分配列は負の数が1つだけの部分配列であり、0を含む部分配列の積は0になります。最善の選択は部分配列 [0] です。

発展問題

最適な部分配列の開始位置と終了位置も、O(n) 時間、O(1) 空間で求めるにはどうすればよいでしょうか？

ヒント

1つずつ開いてください。開くたびに少しずつ答えに近づきます。

3個中0個を表示

解説

負の数を掛けると積の大小関係が逆転するため、これまでの最小の積が次のステップで最大になることがあり、0を掛けるとすべての積が0になります。各インデックスで値を1つではなく2つ、つまりその位置で終わる部分配列の最大の積と最小の積を保持すれば、1回の走査で十分です。

各開始位置からのすべての部分配列を掛け合わせる

正しいが、最大のテストでは終わらない

考え方

開始インデックスを固定し、終了インデックスを右に移動させながら、累積した product に新しい要素を1つずつ掛けます。各ステップの後に最良の値と比較することで、すべての部分配列を1回ずつ確認できます。答えが負になることもあるため、best は nums[0] で初期化します。

開始位置と終了位置の組み合わせは約 n²/2 個あり、それぞれで1回乗算します。要素数が20,000の場合、2 × 10^8 回です。

アルゴリズム

best を nums[0] に設定します。
各 start について、product を 1 に設定します。
end を start から最後のインデックスまで動かし、product に nums[end] を掛けます。
product が best より大きければ、その値を保存します。
best を返します。

def maxProduct(nums):
    n = len(nums)
    best = nums[0]
    for start in range(n):
        product = 1
        for end in range(start, n):
            # product is now the product of nums[start..end]
            product *= nums[end]
            if product > best:
                best = product
    return best

両端から走査し、ゼロで再開する

考え方

ゼロは配列を、ゼロを含まない連続区間に分割します。各区間ではすべての値の絶対値が1以上なので、部分配列が長くなっても絶対積が小さくなることはなく、変わるのは符号だけです。負の数が偶数個なら、区間全体が最適です。奇数個なら負の数を1つ除く必要があり、最適な切り方は、最初の負の数とその前のすべてを除くか、最後の負の数とその後のすべてを除くかのどちらかです。どちらの場合も、区間の接尾部分または接頭部分を残します。

左からの走査では積を更新しながら各接頭部分を調べ、0の後で1にリセットします。右からの走査では各接尾部分を調べます。[-2, 3, -4, -1]では、左からの走査で -2、-6、24、-24、右からの走査で -1、4、12、-24 が得られるので、答えは24です。この議論には、すべての非ゼロの値の絶対値が1以上であることが必要で、これは整数なら成り立ちます。

アルゴリズム

best を nums[0] に、product を 1 に設定します。
左から右へ順に進み、各要素を product に掛け、best と product の大きい方を保持します。
product が 0 になったら、次の連続区間を新たに始められるよう、1 に戻します。
再び product を 1 に設定し、同じように右から左へ進みます。
best を返します。

def maxProduct(nums):
    best = nums[0]
    # Left to right: the product of every prefix of each zero-free run
    product = 1
    for num in nums:
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1  # a zero ends the run, the next one starts fresh
    # Right to left: the product of every suffix of each zero-free run
    product = 1
    for num in reversed(nums):
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1
    return best

ここで終わる最大の積と最小の積を追跡する

考え方

インデックス i で終わる各部分配列は、nums[i] 単独か、nums[i] と i-1 で終わる部分配列との積です。nums[i] が負のとき、これらの積の最大値は、i-1 で終わる最小の積から得られます。そこで、現在のインデックスで終わる部分配列の積の最大値と最小値である high と low の両方を保持します。新しい high は num、high × num、low × num の最大値で、新しい low は最小値です。num 単独を選ぶことで、ゼロの後に計算を再開できます。

最初の例では、-2 が来たとき low は -30 であり、-30 × -2 = 60 が high、つまり答えになります。

アルゴリズム

high、low、bestをnums[0]に設定します。
後続の各要素numについて、a = high × numとb = low × numを計算します。
num、a、bのうち最大の値をhighに、最小の値をlowに設定します。
bestとhighのうち大きい方をbestに設定します。
bestを返します。

def maxProduct(nums):
    # high and low: the largest and smallest product of a subarray ending at the current index
    high = low = best = nums[0]
    for num in nums[1:]:
        # Multiply both old values first: a negative num swaps their roles
        a = high * num
        b = low * num
        high = max(num, a, b)
        low = min(num, a, b)
        best = max(best, high)
    return best

落とし穴と境界ケース

最大の積だけを追跡する。最初の例では、-2 を掛けると 60 になる -30 を捨ててしまうため、60 ではなく 4 が返される。
すでに更新された high から新しい low を計算する。どちらかを変更する前に、high × num と low × num を保存する。
best を 0 または 1 で初期化する。部分配列は空にできないため、[-3] は -3 を返さなければならない。
2パス法の左からの走査だけを実行する。[-2, 3, 4] では -2 より大きい値が現れないが、接尾部分配列 [3, 4] の積は 12 になる。
JavaScript、TypeScript、Lua では、0 に負の数を掛けると -0 になり、マイナス記号付きで表示される。返す前に結果に 0 を加える。

よくある質問3

最大積部分配列の時間計算量はどれくらいですか？

各インデックスで終わる最大値と最小値の積を追跡するには、時間計算量が O(n)、空間計算量が O(1) です。2 回の走査で行うプレフィックスとサフィックスの方法も同じ計算量です。各開始位置からすべての部分配列の積を計算すると、時間計算量は O(n²) になります。

Maximum Product Subarray で最小の積が必要なのはなぜですか？

負の数を掛けると、前のインデックスで終わる最小の積が最大の積になります。最大の積だけを保持していると、必要なときにその候補は失われています。[3, -2, -4]では、-4の前の最小の積は-6で、-6 × -4 = 24が答えです。

最大積部分配列は最大部分配列とどう違いますか？

和では、負の累計値は常に不利になるため、各インデックスにつき値は1つで十分です。積では、負の累計値は別の負の数の後に最大値になることがあり、ゼロはすべてをリセットします。そのため、積のバージョンでは各インデックスで最大の積と最小の積を保持します。

def maxProduct(nums):
    # ここにコードを書いてください

テスト #1

テスト #2

テスト #3

引数

nums = [2, -5, 3, -2, 0, 4]

期待される出力

Maximum Product Subarray

関数

制約

例

ヒント

解説

各開始位置からのすべての部分配列を掛け合わせる

両端から走査し、ゼロで再開する

ここで終わる最大の積と最小の積を追跡する

落とし穴と境界ケース

よくある質問3

似た問題