[python]再符号化/株式の最適な購入/販売時点アルゴリズム

質問する
問題リンク-leetcode
1回の取引で生じる最大利益を計算する.
低買い高売の最大利益問題
入力
[7, 1, 5, 3, 6, 4]
しゅつりょく
5
=>2日1買い、5日目6売り、最大利益5
方法

ブルトポス
最初の価格から売買を始め、O(n^2)ですべての利益を計算し、最低価格を求めることができます

カデインアルゴリズム
右に移動し、以前の状態の低点から価格差を計算します.大きい場合は最低価格に置き換えます.
(右に移動し、低点と収益を計算)

コード#コード#

長波(O(n^2)タイムアウト)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_price = 0
        
        for i, price in enumerate(prices):
            for j in range(i, len(prices)):
                max_price = max(prices[j] - price, max_price)
            
        return max_price

アルゴリズム(O(n)

)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        min_price = sys.maxsize
        
        for price in prices:
            min_price = min(min_price, price)
            profit = max(profit, price - min_price)
        
        return profit

リファレンス
Pythonアルゴリズムインタビュー