leetcode | 188. Best Time to Buy and Sell Stock IV

题目

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
           

Example 2:

Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
           

思路与解法

这道题目在Best Time to Buy and Sell Stock III的基础上放宽了限制，我们可以进行多次买进卖出来得到最大收益。所以我们便不可以像之前那样采用顺序和倒序遍历来计算两次交易获得的最大利润。相反，我们可以采用动态规划的思想：

定义

buy[i]

表示第

i

笔交易买进时自己所剩下的钱；

sell[i]

表示第

i

笔交易卖出时自己所剩下的钱，则状态转移方程如下：

// 买进、不买进选取最大值
buy[i] = max(buy[i], sell[i-1]-price)
// 卖出、不卖出选取最大值
sell[i] = max(sell[i], buy[i]+price)
           

代码实现

const INT_MIN = ^int(^uint(0) >> 1)
func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}
func maxProfit(k int, prices []int) int {
    if k > len(prices) {
		profit := 0
		for i:=0; i<len(prices)-1; i++ {
			if prices[i+1] > prices[i] {
				profit += prices[i+1] - prices[i]
			}
		}
		return profit
	}
	buy := make([]int, k+1)
	sell := make([]int, k+1)
	for i:=0; i<=k;i++ {
		buy[i] = INT_MIN
	}
	for _, price := range prices {
		for i := 1; i <= k; i++ {
			buy[i] = max(buy[i], sell[i-1]-price)
			sell[i] = max(sell[i], buy[i]+price)
		}
	}
	return sell[k]
}
           

遇到的问题

1. buy数据的初始值应该设置为十分小的数值，举例说明，对第一笔交易来说：

   buy[1] = max(buy[1], sell[0]-price)

   ，如果买进，则最终剩下的钱为

   -price

   ，假如之前我们buy数组的初始值设置为0，则buy[1]必定为0，不论买入或者不买入。
2. k值可能会非常大，导致buy和sell数组溢出：

   

   所以，我们可以加上判断，当

   k>len(prices)/2

   时，相当于我们可以进行无数次交易（一次交易至少需要两天），此时我们可以不必定义数组即可获得最终收益。