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

   時，相當于我們可以進行無數次交易（一次交易至少需要兩天），此時我們可以不必定義數組即可獲得最終收益。