7장_12 배열(주식을 사고 팔기 가장 좋은 시점)

한번의 거래로 낼 수 있는 최대의 이익을 계산하라.

기대값이 5인 이유는 1일 때 사서 6에 팔면 5의 이익이 가장 크기 때문이다.

1. 브루트 포스로 계산

가장 간단한 방법은 브루트 포스로 사고 팔고를 반복하여 최대의 이익을 내는 값을 뽑아 내면 되는 방식이다.

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