121. Best Time to Buy and Sell Stock

문제

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

예제 입출력

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

참고

문제 전문은 여기에서 읽으실 수 있습니다.

풀이 1

접근법

1. 오늘의 주가가 어제보다 올랐다면, 최대 이익은 증가합니다.
2. 그러나 만약 오늘의 주가가 어제보다 낮다면, 다음 2가지 경우를 고려해야 합니다:
   1. 오늘의 주가가 기존의 최저가보다는 높은 경우.
   2. 오늘의 주가가 기존의 최저가보다 더 낮은 경우.
3. 만약 2번째 경우라면, 최대 이익을 기준하는 기준이 바뀝니다. 따라서 최저가를 갱신해 줍니다.

구현 코드

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = 10001
        max_profit = 0

        for price in prices:
            if min_price > price:
                min_price = price

            if (price - min_price) > max_profit:
                max_profit = price - min_price

        return max_profit

복잡도 분석

• $n$: prices 의 길이
• 시간 복잡도: $O(n)$
• 공간 복잡도: $O(1)$

---

책에 있는 풀이

참고

원본 코드는 여기에서 확인하실 수 있습니다.

풀이 2

접근법

1. 완전탐색으로 접근합니다.

구현 코드

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_price = 0

        for i, price in enumerate(prices):
            for j in range(i, len(prices)):
                max_price = max(prices[j] - price, max_price)

        return max_price

풀이 3

접근법

1. 풀이 1 과 유사합니다.
2. sys.maximize 로 최솟값을 초기화합니다.

구현 코드

import sys
from typing import List


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        min_price = sys.maxsize

        for price in prices:
            min_price = min(min_price, price)
            profit = max(profit, price - min_price)

        return profit