121. Best Time to Buy and Sell Stock

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

Best Time to Buy and Sell Stock - LeetCode

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가 나는지에 대한 유무는 확인하지 못했다.