LeetCode 121. (Easy) Best Time to Buy and Sell Stock - 주식을 사고팔기 가장 좋은 시점 (python)

문제

Best Time to Buy and Sell Stock - LeetCode

 

예제

Input: prices = [7,1,5,3,6,4]
Output: 5

Constraints:
1 <= prices.length <= 105
0 <= prices[i] <= 104

주식이 1인 시점에서 6인 시점에 팔아야 최대 이득을 볼 수 있고 이득은 5이다.

브루트포스로 풀면 O(n^2)으로 제출 시 타임아웃 에러가 난다.

 

주식의 최소값과 이득을 계속해서 갱신하는 방법으로 O(n)에 해결해야 하는 문제이다.

 

 

풀이

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        minp = sys.maxsize
        
        for p in prices:
            minp = min(p, minp) #최소값 갱신
            result = max(result, p-minp) #이득 갱신
        
        return result

결과