[LeetCode解法] 122. Best Time to Buy and Sell Stock II

問題の説明

Best Time to Buy and Sell Stock II

複数回の取引によって株を買って売ることで得られる最大の利益を計算します。 Best Time to Buy and Sell Stockとは異なり、この問題では複数回の取引が許されています。

解法

アプローチ

この問題はリストをグラフとして視覚化することで簡単に解決できます。株のグラフとして表現すると、変転点を把握して利益を蓄積できます。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        low = prices[0]     # 最初の価格を最低価格として設定
        before = prices[0]  # 直前の価格を初期化
        acc = 0             # 累積利益を初期化

        # pricesを繰り返す
        for v in prices:
            # 現在の価格が直前の価格以上の場合は続行
            if before <= v:
                before = v
                continue

            # 現在の価格が直前の価格よりも小さい場合は、累積利益を更新し、最低価格と直前の価格を現在の価格に設定します。
            acc += before - low
            before = low = v

        # 最後に残った部分のために累積利益を更新します。
        acc += before - low
        return acc

この解法の時間複雑度と空間複雑度は次のとおりです。

• 時間複雑度：O(N)
  • pricesをループするため、時間複雑度はO(N)です。
• 空間複雑度：O(1)
  • 追加のスペースは使用されていません。