package main

func maxProfitFor2(prices []int) (profit int) {
	if len(prices) <= 1 {
		return 0
	}
	K := 2
	dp := make([][]int, K+1) // For k transactions
	for i := range dp {
		dp[i] = make([]int, len(prices))
	}
	for k := 1; k <= K; k++ {
		tmpMax := dp[k-1][0] - prices[0]
		for i := 1; i < len(prices); i++ {
			// if not sell stock at day i, dp[k][i] = dp[k][i-1]
			// else, dp[k][i] = max(dp[k-1][j] + prices[i] - prices[j]), j in [0, i-1]
			// ie. dp[k][i] = prices[i] + max(dp[k-1][j] - prices[j]), j in [0, i-1]
			dp[k][i] = maxInt(dp[k][i-1], prices[i]+tmpMax)
			tmpMax = maxInt(tmpMax, dp[k-1][i]-prices[i])
			profit = maxInt(profit, dp[k][i])
		}
	}
	return
}

// func main() {
// 	println(maxProfit([]int{3, 3, 5, 0, 0, 3, 1, 4}), 6)
// 	println(maxProfit([]int{1, 2, 3, 4, 5}), 4)
// }