LeetCode Top Interview 150) Best Time to Buy and Sell Stock

Question

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.

Constraints:

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

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

---

---

주식 가격을 시간순으로 저장한 리스트 prices를 통해 한 번만 사고 팔 때 가장 높은 이익을 찾아 이익을 반환하는 문제입니다.

제가 생각한 코드는 다음과 같습니다.

        max_profit = 0
        min_price, max_price = prices[0], prices[0]

        for idx,now_price in enumerate(prices[1:],start=1):
            if now_price < min_price:
                min_price, max_price = now_price, now_price
                
            elif max_price < now_price:
                max_profit = max(now_price-min_price,max_profit)
                max_price = now_price
        return max_profit

• max_profit : 최대 이익을 저장하는 변수입니다.
• min_price,max_price : 특정 지점에서의 최소,최댓값 입니다.
• 첫 원소의 가격을 최소,최댓값으로 초기화하고 두번째 원소부터 순회를 시작합니다.
• 현재 가격이 지금까지의 최솟값보다 작다면 최솟값을 현재 값으로 저장합니다.
• 그렇지 않고 현재 가격이 최댓값보다 크다면 최솟값과의 차이와 max_profit중 큰 값을 max_profit으로 저장합니다. 이후 max_price를 현재 값으로 저장합니다.
• 순회가 끝나면 최댓값이 저장되어 있는 max_profit을 반환합니다.

순회를 하며 가장 큰 값과 가장 작은 값을 찾지만 둘의 차이만 찾아서는 안됩니다.
만약 최댓값이 나온 이후 최솟값이 나타난다면 두 가격으로는 사고팔고가 안되니까요!

그래서 새로운 최댓값이 나타날 때만 이전 최대 최소의 차이인 max_profit과 비교합니다. 차이가 가장 큰 쌍을 찾는 것이 목적이기 때문입니다.