Leetcode 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.

Example 1:

Input: prices = [7,6,4,3,1] Output: 0

Explanation: In this case, no transactions are done and the max profit = 0.

Example 2:

Input: root1 = [1], root2 = [1,2]

Output: [2,2]

해설

입력한 배열은 각 시점의 주식의 가격을 나타낸다. 한 시점에서 주식을 사서 그 이후에 어떤 시점에 팔았을 때 이득을 가장 크게 볼 수 있는 값을 구하는 문제이다.

class Solution(object):
    def maxProfit(self, prices):
        max_profit, min_price = 0, float('inf')
        # 각 배열을 돌며 각 시점의 가장 큰 이익을 찾아낸다.
        # 첫 번째 루프에서는 prices 배열의 첫 번째 값이 min_prices 이고 profit 과 max_profit 은 0 이 입력된다.
        # 두 번째 부터 새로운 price 값을 비교해 min_price 값을 찾고 그 때의 profit을 비교하여 max_profit을 찾는 방식이다. 
        for price in prices:
            min_price = min(min_price, price)
            profit = price - min_price
            max_profit = max(max_profit, profit)
        return max_profit