動的計画法で売った次の日は買えない決まりの売り買いの利益を最大にする

動的計画法 (DP)問題 137

毎日の値段の並びで、何回でも売り買いできるが売った次の日は休む決まりのとき、利益の最大を求めます。持っている、今日売った、休んでいるの 3 つの状態を日ごとに持ち歩く練習です。

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

問題

ある品物の毎日の値段が、並び prices で与えられます。prices[i] は i 日目の値段です。次の決まりで売り買いをするとき、得られる利益のいちばん大きい値を返す関数を書いてください。

1 日に、買うか売るか何もしないかのどれか 1 つだけをします
持てる品物は 1 つまでです。持っている間は買えず、持っていなければ売れません
売った次の日は休みで、買えません (その次の日からは買えます)
売り買いは何回してもかまいません。1 回もしなければ利益は 0 です
prices の長さは 1 以上 5000 以下で、どの値段も 0 以上 1000 以下の整数です

入力と出力の例

例 1

0 日目に 4 で買って 1 日目に 9 で売り、2 日目は休みます。3 日目に 2 で買って 4 日目に 7 で売り、5 と 5 で 10 です。

prices = [4, 9, 8, 2, 7]

例 2

休みが無ければ 2 で買って 6 で売り、3 で買って 8 で売る 9 ですが、6 で売った次の日の 3 では買えません。2 で買って 8 で売る 6 がいちばん大きくなります。

prices = [2, 6, 3, 8]

例 3

値段が下がり続けるので、売り買いしないのがいちばんです。

prices = [9, 7, 4, 1]

面接での聞かれ方

面接では、1 回だけ売り買いする株の問題の続きとして、決まりを足して出されます。

「何回でも売り買いできますが、売った翌日は買えません。最大の利益は？」
最初に「同じ日に売って買えますか？」「休みは売った次の 1 日だけですか？」と確かめられるかを見られます
書き終えると「状態の移り方を図で説明してください」と言われることがあります

日ごとに「どの状態にいるか」を決めて、状態の移り方を書き出せるかが見どころです。

ヒント

まだ開いていません

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

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

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

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

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

まず考える手順

段 1

毎日「買う、売る、何もしない」を全部試すと、日数に対して指数的に増えます。5000 日では終わりません。

段 2

ある日の終わりに、自分は次の 3 つのどれかの状態にいます。品物を持っている (hold)、今日売ったばかり (sold)、持っておらず今日は売っていない (rest)。それぞれの状態での、ここまでの利益の最大を持ち歩きます。

段 3

今日の値段を x として、3 つは前の日の 3 つから決まります。

hold は、前から持っていた (前の hold) か、休みでない日から今日買った (前の rest から x を引く) の大きいほう
sold は、前に持っていた物を今日売った (前の hold に x を足す)
rest は、前も rest か、前の日に売った (前の sold。今日が休みの日) の大きいほう

前の日の sold からは、今日買えません。ここが休みの決まりです。

段 4

始めはまだ何も持っていないので、hold はあり得ない状態として、とても小さい値にします。sold と rest は 0 です。最後の日の終わりに品物を持っていても得にならないので、答えは sold と rest の大きいほうです。

解答

Python

def cooldown_profit(prices):
    hold = -10**9
    sold = 0
    rest = 0
    for x in prices:
        prev_hold = hold
        buy = rest - x
        hold = max(hold, buy)
        rest = max(rest, sold)
        sold = prev_hold + x
    return max(sold, rest)

JavaScript

function cooldownProfit(
  prices,
) {
  let hold = -1e9;
  let sold = 0;
  let rest = 0;
  for (const x of prices) {
    const prevHold = hold;
    const buy = rest - x;
    hold = Math.max(hold, buy);
    rest = Math.max(rest, sold);
    sold = prevHold + x;
  }
  return Math.max(sold, rest);
}

Go

func cooldownProfit(
	prices []int,
) int {
	hold := -1000000000
	sold := 0
	rest := 0
	for _, x := range prices {
		prevHold := hold
		buy := rest - x
		hold = max(hold, buy)
		rest = max(rest, sold)
		sold = prevHold + x
	}
	return max(sold, rest)
}

書き換える順に気をつけています。hold は前の日の rest から買う buy を使うので、rest を書き換える前に求めます。rest は前の日の sold を使うので、sold を書き換える前に求めます。sold は前の日の hold を使うので、書き換える前の値を prevHold に取っておきます。

計算量

時間は O(n) です (n は日数)。1 日ずつ 1 回見ます
使う記憶は O(1) です。持つのは 3 つの状態だけです
日ごとに 3 つの状態の表を全部持つ書き方も時間は同じで、記憶が O(n) になります

よくある間違い

売った次の日に買えるようにしてしまう。 hold を前の sold から作ると休みの決まりが消え、例 2 で 9 を返します
書き換えの順を誤る。 rest を先に書き換えてから hold を求めると、今日売ったばかりの利益で今日買えたことになります。3 つとも前の日の値から作られているかを確かめます
値の上がる日を全部足す。休みの無い問題ならそれで合いますが、この問題では上がった日をつなぐと休みの日に買うことがあり、例 2 のように多すぎる答えになります

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

main.py

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

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

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

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


# 「実行」を押すと、この行の結果が出ます
print(cooldown_profit([4, 9, 8, 2, 7]))

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