LeetCode / Best Time to Buy and Sell Stock

（ブログ記事からの転載）

東京都内在住の私ですが、ひとり開発合宿なるものをやってみようと思い、とある県のホテルに泊まって、部屋から出ず黙々とコードの写経をしています。

しかし、ひとり開発合宿は、自分に対する甘えを断ち切れる精神の持ち主でないと、あまり向いていないですね。
ついLeetCodeに浮気してしまいました。

次からはコワーキングスペースに突撃してみたいと思います。

さて、今日の問題。

[https://leetcode.com/problems/best-time-to-buy-and-sell-stock/]

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Example 2:

最も安い時に買い、高い時に売りぬけることで、最大の利益はいくらになるか算出する問題です。
現実には先々の値段がわかっていることはまずないですが、相当精度の高い時系列予測モデルができていればワンチャン？なアルゴリズムですかね。

解答・解説

解法1

解法を思いつくのは難しく無いと思います。
今回の問題は時間計算量はどう頑張っても[tex:O(n)]というところなのでアルゴリズムの比較はせず、簡潔なコードとイマイチなコードを並べておきます。

まずは私のsubmitしたコード。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans = 0
        if prices:
            buy = prices[0]
            for price in prices[1:]:
                if price < buy:
                    buy = price
                if price - buy > ans:
                    sell = price
                    ans = sell - buy
        return ans

コードの意味は非常にシンプルで、買値buyは安い値段があれば置き換え、売値sellは利益ansを超える利益が出るようなら置き換える、という操作を要素数分繰り返しているだけです。

続いてDiscussionで見つけた5 lines solution。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit, min_price = 0, float('inf')
        for price in prices:
            min_price = min(min_price, price)
            profit = price - min_price
            max_profit = max(max_profit, profit)
        return max_profit

コードの意味は私のsubmitしたものと同じですが、とても簡潔ですね。
特に、初期値を max_profit, min_price = 0, float('inf') と設定するところがまだ自分には思いつきませんでした。