動的計画法で最大と最小の積を持ち歩き、積が最大の続いた区間を求める

動的計画法 (DP)問題 135

負の数と 0 を含む整数の並びから、続いた区間の積のうち最も大きい値を求めます。負の数を掛けると大小が入れ替わるので、そこで終わる区間の最大と最小を 2 つ並べて持ち歩く練習です。

海外で定番の問題リスト 4 本には入っていません

問題

整数の並び nums を受け取ります。nums の続いた区間 (1 つ以上の要素) の積のうち、いちばん大きい値を返す関数を書いてください。

区間は 1 つ以上の要素を含みます。空の区間は選べません
nums の長さは 1 以上 1000 以下で、どの値も -10 以上 10 以下の整数です
nums の先頭から、または末尾からのどの区間の積も、-2^31 以上 2^31 未満に収まるものとします

入力と出力の例

例 1

負の数が 2 つあるので、全部を掛けると正の 24 になります。

nums = [2, -3, -4, 1]

例 2

全部を掛けると負の数が 3 つで -60 です。最後の 3 つ [4, -1, -5] の 20 がいちばん大きくなります。

nums = [3, -1, 4, -1, -5]

例 3

0 をまたぐ区間の積は 0 です。負の数だけの区間はどれも 0 より小さいので、0 だけの区間の 0 が答えです。

nums = [-2, 0, -1]

面接での聞かれ方

面接では、最大部分配列和 (和が最大の区間) を解いた人への続きとして出されます。

「続いた区間の積が最大になる値を返してください」
和の書き方をそのまま積に替えて書くと、「負の数が 2 つあったら？」と聞き返されます
「0 があったら？」「全部が負なら？」と、端の場合を順に聞かれることが多いです

和と違って、悪い値 (いちばん小さい負の数) が次の 1 歩で最大に化けるのが、この問題の芯です。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「動的計画法 (DP)」に、この型の要点を表とコードでまとめています。

動的計画法は、途中の答えを覚えておいて、同じ計算をやり直さない書き方です。漸化式で言い直せる問題が多いです。

数学1-2 シグマと漸化式
CS2-9 動的計画法

まず考える手順

段 1

始まりと終わりの組を全部取り、積を計算すると O(n²) です。1000 要素なら 50 万組ほどで答えは出ますが、面接ではもう一段速い O(n) を求められます。

段 2

和の問題では「i 番目で終わる区間の最大」だけを持ち歩けば足りました。積では足りません。i 番目で終わる区間の最小が大きな負の数なら、次に負の数を掛けると大きな正の数になるからです。

段 3

そこで、i 番目で終わる区間の積の最大 hi と最小 lo を 2 つ持ちます。次の値 x で終わる区間は、x だけの区間、hi × x、lo × x の 3 つのどれかです。3 つの最大が新しい hi、最小が新しい lo です。x が 0 なら両方 0 になり、そこで区間が切れたのと同じ形になります。

段 4

各位置での hi の最大を答えとして覚えておきます。始めは 1 つ目の要素だけの区間で、hi、lo、答えのどれも nums[0] です。

解答

Python

def max_product(nums):
    hi = lo = best = nums[0]
    for x in nums[1:]:
        a = hi * x
        b = lo * x
        hi = max(x, a, b)
        lo = min(x, a, b)
        best = max(best, hi)
    return best

JavaScript

function maxProduct(nums) {
  let hi = nums[0];
  let lo = nums[0];
  let best = nums[0];
  const rest = nums.slice(1);
  for (const x of rest) {
    const a = hi * x;
    const b = lo * x;
    hi = Math.max(x, a, b);
    lo = Math.min(x, a, b);
    best = Math.max(best, hi);
  }
  return best;
}

Go

func maxProduct(
	nums []int,
) int {
	hi := nums[0]
	lo, best := hi, hi
	for _, x := range nums[1:] {
		a := hi * x
		b := lo * x
		hi = max(x, a, b)
		lo = min(x, a, b)
		best = max(best, hi)
	}
	return best
}

a と b を先に計算してから hi と lo を書き換えています。hi を先に書き換えると、lo の計算に新しい hi が混ざってしまうからです。

計算量

時間は O(n) です (n は nums の長さ)。1 つずつ 1 回見ます
使う記憶は O(1) です。持つのは hi、lo、答えの 3 つだけです
段 1 の全部の組を試す書き方は、時間が O(n²) です

よくある間違い

最大だけを持ち歩く。和と同じ形で hi だけを持つと、例 1 で 12 を返します。-3 の所で最小の -6 を捨ててしまい、次の -4 と掛けた 24 が作れないからです
hi を先に書き換えてから lo を計算する。 書き換えた後の hi で lo を求めると、x が負のときに大小がずれます。例 2 で 20 にならなければ、まずここを見ます
答えの始めを 0 にする。 nums = [-3] のように負の数が 1 つだけのとき、0 を返してしまいます。空の区間は選べないので -3 が答えです

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def max_product(nums: list[int]) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(max_product([2, -3, -4, 1]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します