(Python) 알고리즘 D+10

문제

prices는 배열이며, 각 요소는 매일의 주식 가격입니다.
만약 한 번만 거래할 수 있다면 = 사고 팔 수 있다면,
제일 큰 이익은 얼마일까요?

Input: [7,1,5,3,6,4]
Output: 5
설명:
2일(가격=1)에 샀다가 5일(가격=6)에 사는 것이 6-1이라 제일 큰 수익.
먼저 사야 팔 수 있습니다.

해답

def maxProfit(prices):
    n = len(prices)
    if n <= 1:
        return 0
    
    maxprofit = 0
    low = prices[0]                 # initial is 5
    for i in range(1, n):           # (1,4)
        low = min(low, prices[i])   # 5, 1
        maxprofit = max(maxprofit, prices[i] - low) # 3
    return maxprofit   # 3
    
>>> prices = [5,8,1,2]
>>> maxProfit(prices) # returns 3 

• prices 의 길이가 1보다 작을 경우, 사고 팔수 없으므로 이익은 0.

• 첫날의 가격을 low로 설정 후, for문을 돌면서 새로운 low를 찾음.

  • 둘째날 가격부터 비교하므로, range(1,n)

  • min함수를 사용하여, 새로운 low를 찾아 설정

• 해당 인덱스의 값과 그 시점의 low값의 차익 vs maxprofit 을 비교하여, 둘 중 높은 값을 max를 사용하여 maxprofit으로 설정.