[LeetCode] 123. Best Time to Buy and Sell Stock III

Problem : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

Consider splitting the input array into 2 parts,  prices[:i] and prices[i:]. 

Let left[i] be the maximum profit can be made by ending on day i.

Let right[i] be the maximum profit can be made by starting on day i

Then the maximum profit can be made by 2 transactions = Max( left[i-1] + right[i] )

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        N = len(prices)
        
        left = [0] * N
        mi = prices[0]
        
        for i in range(1, N):
            left[i] = max(left[i-1], prices[i] - mi)
            mi = min(mi, prices[i])
        
        right = [0] * N
        mx = prices[N-1]
        
        for i in reversed(range(N-1)):
            right[i] = max(right[i+1], mx - prices[i])
            mx = max(mx, prices[i])
        
        result =0
        
        for i in range(N):
            if i == 0:
                result = max(result, right[i])
            elif i == N-1:
                result = max(result, left[i])
            else:
                result = max(result, left[i-1] + right[i])
     
        return result

Edited on 10/15/2021. Fix the logic error in previous code.