第7章12行(株の購入と売却に最適なタイミング)

1239 ワード
パイ アルゴリズム#アルゴリズム# テキストリンク
1回の取引で生じる最大利益を計算する.

期待値が5の理由は1のときに6を買うと5の利益が最大になるからです.

1.Brout Forceで計算


最も簡単な方法は、ブルートフォスで売買を繰り返し、その中から最大の利益の値を抽出することです.
from typing import List


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

しかし、李芳植は一時停止で解除されることはない.別の方法が必要です.

2.低点と現在値の差を計算する


現在の値を指すポインタが右に移動すると、以前の状態の低点から価格差を計算することができ、大きい場合は最大値を反復し続け、最大の収益を得ることができます.
import sys
from typing import List


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
21.07.13
TIL 2021.7.21