123.-best-time-to-buy-and-sell-stock-iii.md

123. Best Time to Buy and Sell Stock III

• Hard

• 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).

Analysis

Consider the questions we had similar to this, for each node, we are considering two things.

1. If price<buy => This means that buying at this point is better than buying at the previous point
2. If price-buy>profit => This means that selling at this point gives more profit than selling at the previous best location.

If we are only to buy once, then we only have to find the largest 'profit' from above. However, in this question, we can buy at most twice. That might lead us to the simple idea of repeating the process above by using buy1 & buy2.

Yet we need to find a way to judge if we are making the best choice, that is to say, we want a parameter that combines the total profit and we can find our solution by maximizing it.

The idea is simple, instead of caculating the individual profit of the second round, we can combine it with the first round. By setting the price of the second round to be 'buy2-profit1', we can calculate and profit=sell2-(buy2-profit1)=profit1+profit2.

Solution (Python)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy1,buy2=float('inf'),float('inf')
        profit1,profit2=0,0
        for i in prices:
            buy1=min(i,buy1)
            profit1=max(profit1,i-buy1)
            
            buy2=min(i-profit1,buy2)
            profit2=max(profit2,i-buy2)
        return profit2