121. Best Time to Buy and Sell Stock

원문: https://doljae.tistory.com/93

leetcode.com/problems/best-time-to-buy-and-sell-stock/

 [Best Time to Buy and Sell Stock - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)

1. 선형 탐색

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_val, profit = prices[0], 0
        for price in prices:
            min_val = min(min_val, price)
            if profit < price - min_val:
                profit = price - min_val
        return profit

최대 이익은 (구매 시점 이후의 최댓값 - 구매 시점의 값) 이 최대가 되는 값이다.

결국 구간에서 선형 탐색을 하면 최소 구매 가격을 찾을 수 있고, 갱신할 수 있다.

(현재 가격 - 최소 구매 가격) 이 최대인 경우를 반환하면 되기 때문에 모든 과정을 선형 탐색으로 해결할 수 있다.

Brute-Force 스타일로 해결했을 때 TLE가 나는지에 대한 유무는 확인하지 못했다.