[Leetcode/파이썬]123. Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III

---

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

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

 

Example 1:

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

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.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

 

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 105

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        transactions1, transactions2 = 10**5, 10**5
        profit1, profit2 = 0, 0

        for price in prices :
            transactions1 = min(price, transactions1)
            profit1 = max(profit1, price - transactions1)

            transactions2 = min(price - profit1, transactions2)
            profit2 = max(profit2, price - transactions2)

        return profit2

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[10**5, 0] * 2 for _ in range(len(prices))]

        for i in range(len(prices)) :
            dp[i][0] = min(dp[i-1][0], prices[i])
            dp[i][1] = max(dp[i-1][1], prices[i] - dp[i-1][0])
            dp[i][2] = min(dp[i-1][2], prices[i] - dp[i-1][1])
            dp[i][3] = max(dp[i-1][3], prices[i] - dp[i-1][2])
        
        return dp[-1][3]

DP 테이블을 직접 만들어 보면서, 위 코드를 이해하려고 하였다.

현재 거래하는 것이 최선의 선택인가에 대해서 판단하는 것이 transactions 이고, 실행하였을 때 얼마나 이득을 남기는 것을 계산한 것이 profit이 되겠다.

첫번째 거래 이윤이 가장 최대가 되는 지점을 찾아서 기억해두었다가, 두번째 거래 이윤이 발생하는 지점에서 현재의 가격과 직전에 발생했던 거래 이윤을 계산한다. 

이윤이 가장 많이 남으면 transactions2에서 적은 수가 기록이 될 것이고, profit2에서 가장 큰 이윤이 기록될 것이다. 결과적으로 놓고 보면 profit2 는 price + profit1 이 된다.

수학적으로 조금 더 머리를 써봤더라면 이런 식은 쉽게 구현할 수 있을 것이고, 프로그래밍 언어로의 구현만 생각하면 어려운 문제이지만 쉽게 해결할 수 있을 것이다.