123. 买卖股票的最佳时机Ⅲ

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例1:

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。
     随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。

示例2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。   
     因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票

示例3:

输入: [7,6,4,3,1] 
输出: 0 
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

解题

我们可以将整个过程分为5个状态,如图:

状态
状态

因此结果是1,3,5中的最大值。

为什么可以用A[i-1] - A[i-2]呢,这举个例子

1 2 3 4 5
这里分为 2-1+3-2+4-3+5-4,他们相加的结果就是5-1

1 2 3 2 5
这里可以变为 2-1+3-2+5-2
为什么呢,因为只取最值,当发现相加结果小时不会保存


func maxProfit(A []int) int {
	n := len(A)
	if n == 0 {
		return 0
	}

	f := make([][]int, n+1)
	f[0] = make([]int, 5+1)
	f[0][1] = 0
	for i := 2; i <= 5; i++ {
		f[0][i] = math.MinInt32
	}

	for i := 1; i <= n; i++ {
		f[i] = make([]int, 6)
		// 1 , 3, 5
		for j := 1; j <= 5; j += 2 {
			f[i][j] = f[i-1][j]
			if j > 1 && i > 1 && f[i-1][j-1] != math.MinInt32 {
			    // 寻找最大的收益
				f[i][j] = Max(f[i][j], f[i-1][j-1]+A[i-1]-A[i-2])
			}
		}
		// 2,4
		for j := 2; j <= 5; j += 2 {
			f[i][j] = f[i-1][j-1]
			if i > 1 && f[i-1][j] != math.MinInt32 {
				f[i][j] = Max(f[i][j], f[i-1][j]+A[i-1]-A[i-2])
			}
			if j > 2 && i > 1 && f[i-1][j-2] != math.MinInt32 {
				f[i][j] = Max(f[i][j], f[i-1][j-2]+A[i-1]-A[i-2])
			}
		}
	}
	return Max(f[n][1], f[n][3], f[n][5])
}

func Max(n ...int) int {
	if len(n) < 0 {
		return 0
	}
	if len(n) == 1 {
		return n[0]
	}
	max := n[0]
	for i := 1; i < len(n); i++ {
		if n[i] > max {
			max = n[i]
		}
	}
	return max
}