【LeetCode】121. Best Time to Buy and Sell Stockを解く

問題へのリンク

問題概要

prices[i]が$i$日目の価格を表すような配列pricesが与えられる．

このとき，株を買う日と売る日をそれぞれ1日ずつ選び利益を最大化する．

戻り値は，取引によって得られる最大の利益とする．ただし，利益が出ない場合は0を返す．

例：

Input: prices = [7,1,5,3,6,4]
Output: 5

２日目に買って，５日目に売ることで

$prices[4] - prices[1] = 6 - 1 = 5$

の利益が得られる．

制約

• $1 \leq prices.length \leq 10^5$
• $0 \leq prices[i] \leq 10^4$

考えたこと

問題を長さ１の配列～長さ$n$の配列の問題へと徐々に拡張しながら解くことで最終的な解が得られそう．

例の問題を用いると以下のようになる：

$n=1$：

Input: [7]
Output: 0

１日だけなので売り買いしても利益は０．

$n=2$：

Input: [7,1]
Output: 0

１日目から2日目にかけて下がっているので０．

$n=3$：

Input: [7,1,5]
Output: prices[1] - prices[2] = 5-1 = 4

これまでで価格が最低だった２日目に買い，３日目に売ると最大の利益４となる．

$n=4$：

Input: [7,1,5,3]
Output: prices[1] - prices[2] = 5-1 = 4

これまでで価格が最低だった２日目に買う．
新たに４日目の価格3が追加されるが，３日目に売った方が利益は大きい．

$n=5$：

Input: [7,1,5,3,6]
Output: prices[4] - prices[2] = 6-1 = 5

これまでで価格が最低だった２日目に買う．
新たに５日目の価格6が追加されており，３日目に売るよりも５日目に売った方が利益は大きい．

$n=6$：

Input: [7,1,5,3,6,4]
Output: prices[4] - prices[2] = 6-1 = 5

これまで価格が最低だった２日目に買う．
新たに６日目の価格4が追加されているが，５日目に売った方が利益は大きい．

従って，5が答えとなる．

以上の考えをまとめると，

• これまでで最大の利益：res
• これまでで最低の価格：min_price

を保持して，pricesを前から順にみていき，

$res = max(res, prices[i]-min\_price)$

を求めることで答えが得られると考えられる．

以上の考えで実装したのが以下のコードである：

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        res = 0
        min_price = prices[0]
        
        for p in prices:
            min_price = min(min_price, p)
            profit = p - min_price
            res = max(res, profit)
        return res