[Leetcode/파이썬]122. Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock II

---

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

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

 

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

 

Constraints:

• 1 <= prices.length <= 3 * 104
• 0 <= prices[i] <= 104

 

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

        for price in prices :
            if current > price :
                current = price
            else :
                res += price - current
                current = price

        return res

이전 문제와 굉장히 유사한 문제라 할 수 있으나, 거래를 여러번 할 수 있다는 점에서 주의할 점이 발생한다.

문제에서 최대 하나의 주식을 보유할 수 있지만, 거래는 여러번 할 수 있다. 

더 간결하게 코드를 정리할 수 있다.

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

        for price in prices :
            if current < price :
                res += price - current
            current = price

        return res

current = price 는 언제나 일어나는 일이기 때문에 다음과 같이 정리할 수 있다.

거래의 횟수 제한이 없기 때문에 현재 가격을 계속해서 갱신하여도 무리가 없고, 현재가격보다 높게 유지가 된다면 이윤에 시세 차익만큼 더하고 가격을 갱신한다. 

그리디 알고리즘의 한 예라고 할 수 있다.