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

buyAndSellStockIII.go

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func maxProfit(prices []int) int {

	if len(prices) <= 1 { // no trade possible
		return 0
	}

	pFirstSellBy := make([]int, len(prices))
	minSoFar := prices[0]

	// do a single pass from left to right, to work out what the max profit
	// is by selling on or before pFirstSellBy[i]
	for i := 1; i < len(prices); i++ {
		pFirstSellBy[i] = max(pFirstSellBy[i-1], prices[i]-minSoFar)
		minSoFar = min(minSoFar, prices[i])
	}

	pSecondSellAfter := pFirstSellBy[len(pFirstSellBy)-1]
	maxInFuture, maxProfitFromSecondTrx := prices[len(prices)-1], 0

	// do another pass to work out what the max profit is from selling before
	// pFirstSellBy[i-1], AND buying on day i and selling in the future
	for i := len(prices) - 2; i > 0; i-- {
		maxProfitFromSecondTrx = max(maxProfitFromSecondTrx, maxInFuture-prices[i])
		maxInFuture = max(maxInFuture, prices[i])
		pSecondSellAfter = max(pSecondSellAfter, pFirstSellBy[i-1]+maxProfitFromSecondTrx)
	}

	return result
}