[파이썬 알고리즘] 주식을 사고팔기 가장 좋은 시점

주식을 사고팔기 가장 좋은 시점

리트코드로 문제 풀러가기

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

입력
[7, 1, 5, 3, 6, 4]
출력
5
설명
 1 일때 사서 6 일때 팔면 5의 이익을 얻는다.

브루트 포스로 푸는 방법도 있지만, 시간 복잡도가 O(n^2)가 되어 풀리지 않는다.

배열을 for 문으로 하나씩 조회하며 저점을 갱신하며 현재 값과의 차이를 저장하여 그 차이 중에서 가장 큰 값을 return 해주면 된다.

# maxprofit.py
def maxProfit(self, prices):
    lowest = prices[0]
    profit = 0

    for price in prices:
        if price < lowest:
            lowest = price

        if profit < (price - lowest):
            profit = price - lowest

    return profit

if 문을 사용하지 않고, min max 연산을 통한 방법도 있었지만 사용하지 않는 쪽이 실행시간과 사용공간 모두에서 더 좋은 결과를 보여주었다.