38. Best Time to Buy and Sell Stock II

読了目安約1分

DP / LeetCode 122 (Medium) — 何回でも売買できる場合の最大利益。隣接差分の和に帰着する。

この章の目次

問題

LeetCode 122. Best Time to Buy and Sell Stock II（Medium / カテゴリ: DP）

前問と同じ株価の配列です。今回は何回でも売買できます。ただし同時に持てる株は 1 つで、売ってから次を買います。得られる利益の最大値を返してください。

考え方

ヒント 1

状態を「i 日目の終わりに株を持っている / 持っていない」の 2 つに分け、それぞれの最大利益で遷移する 2 状態 DP が定石です。持っていない状態の最終値が答えになります。

ヒント 2

この遷移を整理すると、「値上がりする日はすべて拾える」ことが分かります。 prices[i] - prices[i-1] が正になる差分をすべて足した値が答えです。初期条件は利益 0 で、1 パスの走査になります。

Swift 実装のポイント

for i in 1..<prices.count で隣の要素と比較します。要素が 1 個なら空範囲になり、利益 0 のまま返ります。
max(0, diff) を足し込む形にすると if が不要です。
zip(prices, prices.dropFirst()) で隣接ペアを作る書き方もあります。

模範解答

Swift
class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var total = 0
        for i in 1..<prices.count {
            total += max(0, prices[i] - prices[i - 1])
        }
        return total
    }
}

計算量: O(N)。