leetcode筆記：買賣股票問題（2）

04-30

在上篇文章中我們分析了股票買賣問題的遞推條件：

T[i][k][0] = max(T[i-1][k][0],T[i-1][k][1]+prices[i])T[i][k][1] = max(T[i-1][k][1],T[i-1][k-1][0]-prices[i])

針對不同的題目我們可用該遞推條件的不同變種來解決。

1. Best Time to Buy and Sell Stock - LeetCode

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

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]Output: 5max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]Output: 0In this case, no transaction is done, i.e. max profit = 0.

這是股票買賣問題的最基礎版本：給定每日股票價格序列，只允許做1次交易即k=1，求最大收益。本題的遞推條件將k=1帶入即可。由於T[i-1][0][0] = 0，直接將0帶入：

T[i][1][0] = max(T[i-1][1][0],T[i-1][1][1]+prices[i])T[i][1][1] = max(T[i-1][1][1],0-prices[i])

python代碼：

def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ if len(prices) is 0: return 0 T_ik0 = 0 T_ik1 = float(-inf) for i in range(len(prices)): T_ik0 = max([T_ik0,T_ik1+prices[i]]) T_ik1 = max([T_ik1,0-prices[i]]) print(T_ik0,T_ik1) return T_ik0

2.Best Time to Buy and Sell Stock II - LeetCode

第二題與第一題差別在於k變為任意次數，即k= inf，在這種情況下T[i][k-1] = T[i][k]。

T[i][k][0] = max(T[i-1][k][0],T[i-1][k][1]+prices[i])T[i][k][1] = max(T[i-1][k][1],T[i-1][k][0]-prices[i])

python代碼：

3. Best Time to Buy and Sell Stock III - LeetCode

第三題限制k=2，此時我們把第一次和第二次交易的最大收益都加入遞推公式：

T[i][2][0] = max(T[i-1][2][0],T[i-1][2][1]+prices[i])T[i][2][1] = max(T[i-1][2][1],T[i-1][1][0]-prices[i])T[i][1][0] = max(T[i-1][1][0],T[i-1][1][1]+prices[i])T[i][1][1] = max(T[i-1][1][1],-prices[i])

python代碼：

def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ if len(prices) is 0: return 0 T_i20 = 0 T_i21 = float(-inf) T_i10 = 0 T_i11 = float(-inf) for i in range(len(prices)): T_i20 = max([T_i20,T_i21+prices[i]]) T_i21 = max([T_i21,T_i10-prices[i]]) T_i10 = max([T_i10,T_i11+prices[i]]) T_i11 = max([T_i11,0-prices[i]]) #print(T_i20,T_i21,T_i10,T_i11) return T_i20

4.Best Time to Buy and Sell Stock with Cooldown - LeetCode

此題加入限制條件：買賣股票需要間隔一天，新遞推條件：

T[i][k][0] = max(T[i-1][k][0],T[i-1][k][1]+prices[i])T[i][k][1] = max(T[i-1][k][1],T[i-2][k][0]-prices[i])

區別在於將T[i-1][k][0]換成了T[i-2][k][0]來表示購買只能從賣出的後2天開始。

python代碼：

def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ if len(prices) < 2: return 0 T_ik0 = [0 for _ in range(len(prices))] T_ik1 = [float(-inf) for _ in range(len(prices))] for i in range(len(prices)): T_ik0[i] = max([T_ik0[i-1],T_ik1[i-1]+prices[i]]) T_ik1[i] = max([T_ik1[i-1],T_ik0[i-2]-prices[i]]) print(T_ik0[i],T_ik1[i]) return T_ik0[len(prices)-1]

5.Best Time to Buy and Sell Stock IV - LeetCode

本題要在給定k的情況下確定最大收益，由於交易需要2天來完成，所以分為兩種情況：

k>i/2時，等同於k = inf，變為第二題。

k<i/2時，構建數組來儲存每一步操作的最大收益，空間複雜度從O(1)升為O(k)

python代碼：

def maxProfit(self, k, prices): """ :type prices: List[int] :rtype: int """ if len(prices) is 0: return 0 if k is 0: return 0 if k > (len(prices)/2): T_ik0 = 0 T_ik1 = float(-inf) for i in range(len(prices)): T_ik0 = max([T_ik0,T_ik1+prices[i]]) T_ik1 = max([T_ik1,T_ik0-prices[i]]) print(T_ik0,T_ik1) return T_ik0 else: T_ik0 = [0 for _ in range(k)] T_ik1 = [float(-inf) for _ in range(k)] for i in range(len(prices)): for j in range(k-1,-1,-1): #T_ik0_old = T_ik0[j] T_ik0[j] = max([T_ik0[j],T_ik1[j]+prices[i]]) if j is not 0: T_ik1[j] = max([T_ik1[j],T_ik0[j-1]-prices[i]]) else: T_ik1[j] = max([T_ik1[j],0-prices[i]]) return T_ik0[k-1]

6. Best Time to Buy and Sell Stock with Transaction Fee - LeetCode

本題k為任意次數，但加入新條件：交易時收取手續費fee，其實也很簡單，在遞推條件中交易時考慮手續費即可。

T[i][k][0] = max(T[i-1][k][0],T[i-1][k][1]+prices[i])T[i][k][1] = max(T[i-1][k][1],T[i-1][k][0]-prices[i]-fee)

python代碼：

def maxProfit(self, prices, fee): """ :type prices: List[int] :rtype: int """ if len(prices) is 0: return 0 T_ik0 = 0 T_ik1 = float(-inf) for i in range(len(prices)): T_ik0 = max([T_ik0,T_ik1+prices[i]]) T_ik1 = max([T_ik1,T_ik0-prices[i] - fee]) return T_ik0

以上為所有股票買賣問題變種。