【競技プログラミング】「Best Time To Buy And Sell Stock」with Python | LeetCode #121

こちらは「Best Time To Buy And Sell Stock」のPythonによる解答例となっております。この問題は、整数の配列が与えられたときに、その配列内の要素を購入して販売することで得られる最大の利益を求める問題です。

問題

整数の配列 prices が与えられたとき、この配列内の要素を購入して販売することで得られる最大の利益を求めます。ただし、購入価格は販売価格よりも前でなければなりません。

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4

解法

この問題は、配列内の要素を1つずつ処理し、それまでの最小値との差を計算して最大利益を求める方法があります。このアプローチの計算量は O(n) です。

アルゴリズムの概要を以下に述べます。

配列の最初の要素を現在の最小値 min_price として初期化します。
配列を1つずつ反復処理します。
現在の要素と min_price の差を計算し、最大利益 max_profit と比較します。
現在の要素と min_price を比較し、より小さい方を min_price として更新します。
反復処理が終了したら、最大利益を返します。

Pythonコード

以下のコードが、「Best Time to Buy and Sell Stock」を解くためのPythonプログラムとなります。

### Function ##################################################################

def solve(num=0):
    
    solver  = Solution().maxProfit
    
    if 1 <= num <= Input().input: id_LIST = [num]
    else: id_LIST = [id+1 for id in range(Input().input)]
    
    for id in id_LIST:
        data    = Input(id)
        ans     = solver(data.prices)
        result  = "OK" if ans==data.ans else "NG"
        print(f"[{str(id).zfill(3)}] {result}")

### Class #####################################################################

import itertools

class Solution(object):
    
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        
        ### [7,1,5,3,6,4] (current price)
        ### [7,1,1,1,1,1] (min price until current)
        ### [0,0,4,2,5,3] (profit = cur - min)
        
        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
    
    # def maxProfit(self, prices):
    #     """
    #     :type prices: List[int]
    #     :rtype: int
    #     """
        
    #     ### [7,1,5,3,6,4] (current price)
    #     ### [7,1,1,1,1,1] (min price until current)
    #     ### [0,0,4,2,5,3] (profit = cur - min)
        
    #     ### min_price = [val for val in itertools.accumulate(prices, func=min)]
    #     profit_price = [ price-min_price for price, min_price in zip(prices,itertools.accumulate(prices, func=min))]
        
    #     return max(profit_price)

#==============================================================================

class Input:
    
    def __init__(self, num=0):
        
        if num == 1:
            self.prices = [7,1,5,3,6,4]
            self.ans    = 5
        
        elif num == 2:
            self.prices = [7,6,4,3,1]
            self.ans    = 0

        else:
            self.input  = 2

### Main ######################################################################

if __name__ == "__main__":

    solve()

###############################################################################