窓の左端に最安値を置いて 1 回の売り買いの利益を最大にする

日ごとの値段の並びから、1 回だけ買って、それより後の日に 1 回だけ売るときの、いちばん大きい利益を返します。窓の左端をそれまでの最安の日に置き、右端を 1 日ずつ進める練習です。

海外で定番の問題リスト 4 本のうち 4 本に入っています (Blind 75、NeetCode 150、Grind 75、LeetCode Top Interview 150)

問題

ある品物の、日ごとの値段の並び prices を受け取ります。並びの順が日の順です。どこか 1 日に 1 つ買い、それより後のどこか 1 日に売ります。売った値段から買った値段を引いた利益のうち、いちばん大きい値を返す関数を書いてください。

買う日は売る日より前でなければなりません。同じ日に買って売ることはできません
どう売り買いしても利益が出ないときは、売り買いをしないことにして 0 を返します
prices の長さは 1 以上 100000 以下、値段はどれも 0 以上 10000 以下です

入力と出力の例

例 1

値段 2 の日に買い、その次の値段 7 の日に売ると、5 の利益です。

prices = [8, 3, 6, 2, 7, 4]

例 2

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

prices = [9, 7, 4, 1]

例 3

いちばん安い日がいちばん高い日より後にあると、その 2 日では売り買いできません。

prices = [2, 10, 1, 5]

面接での聞かれ方

面接では、株の値動きの場面として短く聞かれることが多いです。

「株価の配列があります。1 回だけ買って売るとき、最大の利益はいくらですか？」
「最安値で買って最高値で売ればよいのでは？」と、わざと落とし穴へ誘う形で聞かれることもあります
書き終えたあとに「何回でも売り買いできたらどうしますか？」と、条件を変えた続きが出ることがあります

最初に、買うのは売るより前であること、利益が出ないときに何を返すかを確かめてから書き始めます。

ヒント

まだ開いていません

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

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

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

まずは素直に、買う日と売る日の組を全部試す書き方を考えます。2 重の繰り返しで、買う日より後の売る日を全部試せば正しく動きます。ただ、長さが 100000 なら組は約 50 億あります。

段 2

売る日を 1 日決めたとき、いちばん得をする買う日は「その日より前で、いちばん安い日」です。だから、前から 1 日ずつ見ながら「ここまでの最安値」を覚えておけば、その日に売ったときの利益はすぐに出せます。

段 3

これを窓として見ます。窓の左端は買う日、右端は売る日です。右端を 1 日ずつ進め、そのたびに窓の両端の値段の差を利益の候補にします。右端の値段が左端より安くなったら、そこから先はこの日に買う方が必ず得なので、左端を右端の位置まで動かします。窓を 1 回なめるだけで、全部の売る日を試したことになります。

解答

Python

def max_profit(prices):
    low = prices[0]
    best = 0
    for p in prices:
        if p < low:
            low = p
        gain = p - low
        if gain > best:
            best = gain
    return best

JavaScript

function maxProfit(prices) {
  let low = prices[0];
  let best = 0;
  for (const p of prices) {
    if (p < low) {
      low = p;
    }
    const gain = p - low;
    if (gain > best) {
      best = gain;
    }
  }
  return best;
}

Go

func maxProfit(
	prices []int,
) int {
	low := prices[0]
	best := 0
	for _, p := range prices {
		if p < low {
			low = p
		}
		gain := p - low
		if gain > best {
			best = gain
		}
	}
	return best
}

low が窓の左端の値段、p が右端の値段です。最安値を先に更新してから差を出すので、その日に買ってその日に売る形は差が 0 になり、答えを増やしません。best を 0 から始めるので、利益が出ないときは 0 が残ります。

計算量

時間は O(n) です。値段の並びを前から 1 回なめるだけです
使う記憶は O(1) です。最安値と、いちばん大きい利益の置き場だけです
段 1 の全部の組を試す書き方は、時間が O(n²) です。「売る日ごとの最安の買う日」を覚えておくことで、組を試す手間が要らなくなりました

よくある間違い

全体の最安値と最高値の差を返す。例 3 の [2, 10, 1, 5] では、最安の 1 は最高の 10 より後なので、9 は答えになりません。買う日は売る日より前です
利益が出ないときに負の数を返す。 best を最初の 2 日の差や、とても小さい数から始めると、例 2 で -2 のような値が残ります。売り買いしない 0 から始めます
長さが 1 のときに 2 日目を読む。 prices[1] から始める書き方は、1 日しか無い並びで並びの外を読みます。prices[0] を最安値にして、全部の日を回します
最安値を変えた日に、前の最安値まで忘れてよいか迷う。新しい最安値より後の日に売るなら、前の最安値で買うより必ず得なので、前の値は要りません。それより前の日の利益は、もう best に入っています

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日

main.py

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

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

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

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


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

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