문제 링크

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

풀이 방법

가장 싼 가격(min_price)와 답이 되는 가장 비싼 이익(max_profit)을 선언해놓고

prices 배열을 돌면서 모든 price를 조사할건데,

min_price는 계속 가장 싼 가격으로 업데이트 되고

max_profit은 현재 price에서 min_price를 파는 값과 기존 max_profit 중 최대값을 업데이트 한다.

모든 가격을 조사한뒤 max_profit을 리턴.

루프가 첫 원소부터 돌고 가장 싼 가격이 업데이트 되고 그 가장 싼 가격에서 현재 가격에 팔면 얼마나 이득인지 계산하므로

팔고 사는게 아닌, 사고 파는 순서가 보장된다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
  def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    max_profit = 0
    min_price = float('inf')
    for price in prices:
      min_price = min(price, min_price)
      profit = price - min_price
      max_profit = max(profit, max_profit)

    return max_profit