Pythonで株を1回だけ売買して得られる最大利益を求めるプログラム

時系列順に並んだ企業の株価リストが与えられたとき、その株を一度だけ買って売ることで得られる最大の利益を求める問題を考えてみましょう。ただし、「売る」ためには必ず先に「買って」おく必要がある点に注意してください。

たとえば、入力が prices = [10, 12, 9, 6, 8, 12] の場合、出力は 6 になります。これは、株価が 6 のときに購入し、12 のときに売却すれば、最大の利益 12 - 6 = 6 が得られるためです。

解法のアプローチ

この問題は、リストを一度走査するだけで解くことができます。ポイントは「これまでの最安値」を常に記録しておき、各時点での売却益を計算して最大値を更新していくことです。具体的には、次の手順に従います。

• max_profit（最大利益）を 0 で初期化する
• min_stock（これまでの最安値）を無限大で初期化する
• prices 内の各価格 price に対して、以下を繰り返す
  • max_profit を「現在の max_profit」と「price − min_stock」のうち大きい方で更新する
  • min_stock を「現在の min_stock」と「price」のうち小さい方で更新する
• 最後に max_profit を返す

この方法なら、全ての組み合わせを調べる O(n²) の素朴な手法と比べて、わずか O(n) の計算量で効率的に答えを求められます。

実装例

理解を深めるために、実際のコードを見てみましょう。

class Solution:
    def solve(self, prices):
        max_profit = 0
        min_stock = float('inf')
        for price in prices:
            max_profit = max(max_profit, price - min_stock)
            min_stock = min(min_stock, price)
        return max_profit

ob = Solution()
print(ob.solve([10, 12, 9, 6, 8, 12]))

入力

[10, 12, 9, 6, 8, 12]

出力

6

コードの解説

このアルゴリズムでは、ループの中でまず「今の価格で売った場合の利益」を計算し、既存の最大利益と比較します。その後、現在の価格がこれまでの最安値より低ければ min_stock を更新します。この順序により、常に「過去の安値で買って、現在の価格で売る」という条件が自然に満たされ、売却が購入より前になる不正な取引を防げます。

なお、株価が単調に下がり続けるようなケースでは利益がマイナスになる可能性がありますが、max_profit を 0 で初期化しているため、その場合は「取引しない（利益 0）」という結果が返されます。