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.

index번째 날짜의 주식 가격이 들어간 prices 배열이 주어진다.
하나의 주식을 샀다 다시 판다고 가정할때, 최대의 수익을 구하시오.

예시

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

제한

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

풀이

가장 오른쪽의 값을 저장 후 바로 왼쪽에 있는 값을 확인한다.
만약, 저장된 값보다 바로 왼쪽에 있는 값이 작다면, 수익을 오른쪽 값 - 왼쪽 값으로 바꾼다.
하지만 왼쪽값이 더 크다면, 이 왼쪽값일때 파는게 더 수익이 크기에 저장된 오른쪽 값을 왼쪽값으로 바꾼다.
이를 0번 index까지 반복하면 된다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        right = prices[len(prices) - 1]

        for i in range(len(prices) - 1, 0, -1):
            if right >= prices[i-1]:
                if right-prices[i-1] > profit:
                    profit = right-prices[i-1]
            else:
                right = prices[i-1]

        return profit