[LeetCode] #188. Best Time to Buy and Sell Stock IV
題目
You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.
Find the maximum profit you can achieve. You may complete at most k transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
直覺解
構想：
先找出所有可以低買高賣的時機，再從這些時機裡面挑出 k 個。挑選方式：while 迴圈，每圈會減少一個時機，減少方式有兩種，合併兩個相鄰的時機，或移除一個時機。
python 3 實作（失敗）：
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
profit = 0
if len(prices) < 2 or k == 0:
return profit
# find all best time to buy and sell stock
start = 0
intervals = []
while start < len(prices):
interval = self.find_buy_sell_interval(start, prices)
if interval['buy'] is None or interval['sell'] is None:
break
interval['subtotal'] = prices[interval['sell']] - prices[interval['buy']]
intervals.append(interval)
start = interval['sell'] + 1
# pick k best time to buy and sell stock
if not intervals:
return profit
while len(intervals) > k:
# merge two intervals, or remove one interval
merge_interval_index = 0
merge_subtotal = prices[intervals[1]['sell']] - prices[intervals[0]['buy']]
for i in range(2, len(intervals)):
new_profit = prices[intervals[i]['sell']] - prices[intervals[i-1]['buy']]
if new_profit > merge_subtotal:
merge_interval_index = i - 1
merge_subtotal = new_profit
min_subtotal_interval_index = 0
min_subtotal = intervals[0]['subtotal']
for i in range(1, len(intervals)):
if intervals[i]['subtotal'] < min_subtotal:
min_subtotal_interval_index = i
min_subtotal = intervals[i]['subtotal']
if merge_subtotal > min_subtotal:
left_interval = intervals.pop(merge_interval_index)
right_interval = intervals.pop(merge_interval_index)
intervals.append({'buy': left_interval['buy'], 'sell': right_interval['sell'], 'subtotal': merge_subtotal})
else:
del intervals[min_subtotal_interval_index]
else:
for interval in intervals:
profit += interval['subtotal']
return profit
@staticmethod
def find_buy_sell_interval(start, prices):
buy_day = None
sell_day = None
# find buy day
min_price_index = start
start += 1
while start < len(prices):
if prices[start] <= prices[min_price_index]:
min_price_index = start
else:
buy_day = min_price_index
break
start += 1
#find sell day
sell_day = start
while start < len(prices):
if prices[start] >= prices[sell_day]:
sell_day = start
else:
break
start += 1
return {'buy': buy_day, 'sell': sell_day}
Submission Detail
Wrong Answer
Input: 2, [1,2,4,2,5,7,2,4,9,0]
Output: 10
Expected: 13
失敗原因
合併兩個相鄰的時機時，挑錯合併的對象。所有能低買高賣的時機為：
price 1 時買，price 4 時賣，獲利 3
price 2 時買，price 7 時賣，獲利 5
price 2 時買，price 9 時賣，獲利 7
總獲利 15
合併兩個相鄰的時機時，我的程式碼把第 2、3 個時機合併了。因為 1、2 合併後變成 price 1 時買，price 7 時賣，獲利 6，而 2、3 合併後變成 price 2 時買，price 9 時賣，獲利 7。我的程式碼挑了能夠帶來最大獲利的那個組合去合併。最終結果變成：
price 1 時買，price 4 時賣，獲利 3
price 2 時買，price 9 時賣，獲利 7
總獲利 10
但解答是把 1、2 合併，最終結果變成：
price 1 時買，price 7 時賣，獲利 6
price 2 時買，price 9 時賣，獲利 7
總獲利 13
構想：
挑選合併的時機時，改成用「怎麼挑選，造成的損失比較小」為標準。
python 3 實作（失敗）：
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
profit = 0
if len(prices) < 2 or k == 0:
return profit
# find all best time to buy and sell stock
start = 0
intervals = []
while start < len(prices):
interval = self.find_buy_sell_interval(start, prices)
if interval['buy'] is None or interval['sell'] is None:
break
interval['subtotal'] = prices[interval['sell']] - prices[interval['buy']]
intervals.append(interval)
start = interval['sell'] + 1
# pick k best time to buy and sell stock
if not intervals:
return profit
while len(intervals) > k:
# merge two intervals, or remove one interval
merge_interval_index = 0
merge_subtotal = prices[intervals[1]['sell']] - prices[intervals[0]['buy']]
merge_loss = intervals[0]['subtotal'] + intervals[1]['subtotal'] - merge_subtotal
for i in range(2, len(intervals)):
new_subtotal = prices[intervals[i]['sell']] - prices[intervals[i-1]['buy']]
new_loss = intervals[i - 1]['subtotal'] + intervals[i]['subtotal'] - new_subtotal
if new_loss < merge_loss:
merge_interval_index = i - 1
merge_loss = new_loss
min_subtotal_interval_index = 0
loss_subtotal = intervals[0]['subtotal']
for i in range(1, len(intervals)):
if intervals[i]['subtotal'] < loss_subtotal:
min_subtotal_interval_index = i
loss_subtotal = intervals[i]['subtotal']
if merge_loss < loss_subtotal:
left_interval = intervals.pop(merge_interval_index)
right_interval = intervals.pop(merge_interval_index)
intervals.append({'buy': left_interval['buy'], 'sell': right_interval['sell'], 'subtotal': merge_subtotal})
else:
del intervals[min_subtotal_interval_index]
else:
for interval in intervals:
profit += interval['subtotal']
return profit
@staticmethod
def find_buy_sell_interval(start, prices):
buy_day = None
sell_day = None
# find buy day
min_price_index = start
start += 1
while start < len(prices):
if prices[start] <= prices[min_price_index]:
min_price_index = start
else:
buy_day = min_price_index
break
start += 1
#find sell day
sell_day = start
while start < len(prices):
if prices[start] >= prices[sell_day]:
sell_day = start
else:
break
start += 1
return {'buy': buy_day, 'sell': sell_day}
Submission Detail
Wrong Answer
Input: 2, [1,2,4,2,5,7,2,4,9,0,9]
Output: 16
Expected: 17
失敗原因
買賣股票的時機清單，我是有按照時間排序的。但我把 merge 後的時機加進去清單時，沒有留意擺放的順序，而是直接加在清單最尾巴。
一開始，挑出了四個低買高賣的時機，這時候清單有依照時間排序：
price 1 時買，price 4 時賣，獲利 3
price 2 時買，price 7 時賣，獲利 5
price 2 時買，price 9 時賣，獲利 7
price 0 時買，price 9 時賣，獲利 9
prices = [1,2,4,2,5,7,2,4,9,0,9]
總獲利 24
因為 k 是 2，只能從中挑兩個時機。第一次挑選結果，是合併上述的 1、2，但合併後的結果，卻是排在時間順序的最後面：
price 2時買，price 9 （day 9）時賣，獲利 7。
price 0 時買，price 9（day 11）時賣，獲利 9。
price 1（day 1）時買，price 7（day 6）時賣，獲利 6。日子都已經過到 day 11 了，這時候還想回去 day 1 買股票，然後在 day 6 時賣掉。
prices = [1,2,4,2,5,7,2,4,9,0,9]
總獲利 22
因為 k 是 2，還需要再刪除一個時機。根據上述合併後的新清單，程式碼做了下列考量：
合併 1、2，變成 price 2（day 7）時買，price 9（day 11）時賣，損失 9。
合併 2、3，變成 price 0（day 10）時買，price 7（day 6）時賣，損失 8。
刪除 3，放棄「price 1（day 1）時買，price 7（day 6）時賣」的機會，損失 6。
prices = [1,2,4,2,5,7,2,4,9,0,9]
三種可能性中，刪除 3 的損失最小，所以決定刪除 3，所以最終的結果是：
price 2 時買，price 9 時賣，獲利 7。賣出的時間是 day 9
price 0 時買，price 9 時賣，獲利 9。賣出的時間是 day 11
prices = [1,2,4,2,5,7,2,4,9,0,9]
總獲利 16
構想：
合併後的時機，放進清單時，要留意放置的位置。
python 3 實作（失敗）：
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
profit = 0
if len(prices) < 2 or k == 0:
return profit
# find all best time to buy and sell stock
start = 0
intervals = []
while start < len(prices):
interval = self.find_buy_sell_interval(start, prices)
if interval['buy'] is None or interval['sell'] is None:
break
interval['subtotal'] = prices[interval['sell']] - prices[interval['buy']]
intervals.append(interval)
start = interval['sell'] + 1
# pick k best time to buy and sell stock
if not intervals:
return profit
while len(intervals) > k:
# merge two intervals, or remove one interval
merge_interval_index = 0
merge_subtotal = prices[intervals[1]['sell']] - prices[intervals[0]['buy']]
merge_loss = intervals[0]['subtotal'] + intervals[1]['subtotal'] - merge_subtotal
for i in range(2, len(intervals)):
new_subtotal = prices[intervals[i]['sell']] - prices[intervals[i-1]['buy']]
new_loss = intervals[i - 1]['subtotal'] + intervals[i]['subtotal'] - new_subtotal
if new_loss < merge_loss:
merge_interval_index = i - 1
merge_loss = new_loss
min_subtotal_interval_index = 0
loss_subtotal = intervals[0]['subtotal']
for i in range(1, len(intervals)):
if intervals[i]['subtotal'] < loss_subtotal:
min_subtotal_interval_index = i
loss_subtotal = intervals[i]['subtotal']
if merge_loss < loss_subtotal:
left_interval = intervals.pop(merge_interval_index)
right_interval = intervals.pop(merge_interval_index)
intervals.insert(merge_interval_index, {'buy': left_interval['buy'], 'sell': right_interval['sell'], 'subtotal': merge_subtotal})
else:
del intervals[min_subtotal_interval_index]
else:
for interval in intervals:
profit += interval['subtotal']
return profit
@staticmethod
def find_buy_sell_interval(start, prices):
buy_day = None
sell_day = None
# find buy day
min_price_index = start
start += 1
while start < len(prices):
if prices[start] <= prices[min_price_index]:
min_price_index = start
else:
buy_day = min_price_index
break
start += 1
#find sell day
sell_day = start
while start < len(prices):
if prices[start] >= prices[sell_day]:
sell_day = start
else:
break
start += 1
return {'buy': buy_day, 'sell': sell_day}
Submission Detail
Wrong Answer
Input: 2, [6,5,4,8,6,8,7,8,9,4,5]
Output: 8
Expected: 7
失敗原因
買賣股票的時機是對的，但計算 profit 時算錯了。最後挑選出的時機如下：
price 4（day 3）時買，price 8（day 4）時賣，獲利 4。
price 6（day 5）時買，price 9（day 9）時賣，獲利 4。但正確的獲利值是 3。
prices = [6,5,4,8,6,8,7,8,9,4,5]
算錯的原因，是因為我在挑選要合併哪兩個 interval 時，只顧著更新 merge_interval_index 和 merge_loss 的值，忘記更新 merge_subtotal，所以 merge_subtotal 一直維持是頭兩個 interval 合併後算出來的獲利值。
構想：
記得一併更新 merge_subtotal。
python 3 實作：
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
profit = 0
if len(prices) < 2 or k == 0:
return profit
# find all best time to buy and sell stock
start = 0
intervals = []
while start < len(prices):
interval = self.find_buy_sell_interval(start, prices)
if interval['buy'] is None or interval['sell'] is None:
break
interval['subtotal'] = prices[interval['sell']] - prices[interval['buy']]
intervals.append(interval)
start = interval['sell'] + 1
# pick k best time to buy and sell stock
if not intervals:
return profit
while len(intervals) > k:
# merge two intervals, or remove one interval
merge_interval_index = 0
merge_subtotal = prices[intervals[1]['sell']] - prices[intervals[0]['buy']]
merge_loss = intervals[0]['subtotal'] + intervals[1]['subtotal'] - merge_subtotal
for i in range(2, len(intervals)):
new_subtotal = prices[intervals[i]['sell']] - prices[intervals[i-1]['buy']]
new_loss = intervals[i - 1]['subtotal'] + intervals[i]['subtotal'] - new_subtotal
if new_loss < merge_loss:
merge_interval_index = i - 1
merge_subtotal = new_subtotal
merge_loss = new_loss
min_subtotal_interval_index = 0
loss_subtotal = intervals[0]['subtotal']
for i in range(1, len(intervals)):
if intervals[i]['subtotal'] < loss_subtotal:
min_subtotal_interval_index = i
loss_subtotal = intervals[i]['subtotal']
if merge_loss < loss_subtotal:
left_interval = intervals.pop(merge_interval_index)
right_interval = intervals.pop(merge_interval_index)
intervals.insert(merge_interval_index, {'buy': left_interval['buy'], 'sell': right_interval['sell'], 'subtotal': merge_subtotal})
else:
del intervals[min_subtotal_interval_index]
else:
for interval in intervals:
profit += interval['subtotal']
return profit
@staticmethod
def find_buy_sell_interval(start, prices):
buy_day = None
sell_day = None
# find buy day
min_price_index = start
start += 1
while start < len(prices):
if prices[start] <= prices[min_price_index]:
min_price_index = start
else:
buy_day = min_price_index
break
start += 1
#find sell day
sell_day = start
while start < len(prices):
if prices[start] >= prices[sell_day]:
sell_day = start
else:
break
start += 1
return {'buy': buy_day, 'sell': sell_day}
效能：
Runtime: 119 ms, faster than 38.45% of Python3 online submissions for Best Time to Buy and Sell Stock IV.
Memory Usage: 14.6 MB, less than 53.23% of Python3 online submissions for Best Time to Buy and Sell Stock IV.
研究別人的解
研究重點：想看更簡潔、更有效率的寫法。
別人的 python 3 實作（加上研究用的 print）：
class Solution:
inf = float('inf')
def cleaned(self, B):
A, c = [B[0]], B[1]
for i in range(1, len(B)-1):
a, b, c = A[-1], c, B[i+1]
if b == a or b == c or (a < b < c) or (a > b > c):
continue
A.append(b)
A.append(B[-1])
return A
def maxProfit(self, k, prices):
# For Problem # 123:
# -> Uncomment k = 2 here, and remove it from the function parameters
# k = 2
# -------------------- Initial Edge Cases --------------------
if not k or len(prices) < 2:
return 0
#
# Clean Prices
prices = self.cleaned(prices)
print('cleaned prices:', prices)
#
# Use all Profits
profits = [prices[i]-prices[i-1]
for i in range(1, len(prices)) if prices[i] > prices[i-1]]
print('all profit:', profits)
if k >= len(profits):
return sum(profits)
#
# -------------------- Main Code --------------------
print('---- Main Code -----')
B = [0]*k
P = [self.inf]*k
i = None
for x in prices:
P[0] = min(P[0], x) # track min-buy point
# track max. profit (buying now at lowest cost)
B[0] = max(B[0], x-P[0])
print('x:', x, 'P:', P, 'B:', B)
print('--begin for--')
for i in range(1, k):
# Min Buy Point Subsidized by "i" Transactions
P[i] = min(P[i], x - B[i-1])
# Subsidized Profits (with current point)
B[i] = max(B[i], x - P[i])
print('i:', i, 'P:', P, 'B:', B)
if B[i] == B[i-1]:
break # We're just copying the previous transactions
print('--end for--')
return B[i] if i != None else B[0]
效能（沒有的 print 的版本）：
Runtime: 60 ms, faster than 98.30% of Python3 online submissions for Best Time to Buy and Sell Stock IV.
Memory Usage: 14.4 MB, less than 58.72% of Python3 online submissions for Best Time to Buy and Sell Stock IV.
研究感想
他的 cleaned 函式，是把所有最能低買高賣的時機都先篩選出來。例如：
price 1 時買，price 4 時賣，獲利 3
price 2 時買，price 7 時賣，獲利 5
price 2 時買，price 9 時賣，獲利 7
price 0 時買，price 9 時賣，獲利 9
prices = [1,2,4,2,5,7,2,4,9,0,9]
所以 cleaned 完的結果是：prices = [1,4,2,7,2,9,0,9]，而 profits 就是 [3, 5, 7, 9]
跟我的 intervals 變數紀錄的事情類似，但是我的 intervals 紀錄得實在太囉唆，連買賣的時機是在 prices 的哪個 index 都要記。明明答案只在乎 profit，不在乎 index，但我還是把 index 的資訊存起來了。
在 P 和 B 的幫助下，迭代過一次 cleaned prices 就可以同時計算「最多只能做 1 次買賣的最大 profit」、「最多只能做 2 次買賣的最大 profit」、⋯⋯、「最多只能做 k 次買賣的最大 profit」，P 的設計真是太神乎其技了。
在「最多只能做 i 次買賣的限制下」（i 是 base 0），B[i] 是紀錄淨利，因為淨利越大越好，所以取最大值。P[i] 跟「在最低價時買股票」有關，但他不是紀錄股票價格，而是紀錄到目前為止買股票的成本（如果買賣股票有賺錢的話，成本可能會變成負數），因為成本越小越好，所以取最小值。這樣講還是挺抽象的，直接看例子比較容易懂：
input 是 k = 2, prices = [1, 2, 4, 2, 5, 7, 2, 4, 9, 0, 9] 時，印出來的東西（其中加入了我的筆記，筆記用粗體表示）：
cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
all profit: [3, 5, 7, 9]
---- Main Code -----
cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
x: 1 P: [1, inf] B: [0, 0]，
現在要決定，最多只能做 1 次買賣的話，買賣股票的時機
結果：在股票價格是 1 的時候買股票，現在還不能賣股票，淨利 0
--begin for--
i: 1 P: [1, 1] B: [0, 0]
現在要決定，最多只能做 2 次買賣的話，2 次買賣股票的時機
第 1 次買賣：在股票價格是 1 的時候買股票，現在還不能賣股票，淨利 0
第 2 次買賣：還不能做第 2 次買賣
--end for--
cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
x: 4 P: [1, 1] B: [3, 0]
現在要決定，最多只能做 1 次買賣的話，買賣股票的時機
結果：在股票價格是 1 的時候買股票，在股票價格是 4 的時候賣股票，淨利 3
--begin for--
i: 1 P: [1, 1] B: [3, 0]
現在要決定，最多只能做 2 次買賣的話，2 次買賣股票的時機
第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 4 的時候賣股票，淨利 3
第 2 次買賣：還不能做第 2 次買賣
--end for--
cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
x: 2 P: [1, 1] B: [3, 3]
現在要決定，最多只能做 1 次買賣的話，買賣股票的時機
結果：在股票價格是 1 的時候買股票，在股票價格是 4 的時候賣股票，淨利 3
--begin for--
i: 1 P: [1, -1] B: [3, 3]
現在要決定，最多只能做 2 次買賣的話，2 次買賣股票的時機
P[1] 是 -1。若比照 B[0] 的時機交易後獲得淨利 3，然後在現在股票價格 2 的時候買股票，會倒賺 1 塊
第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 4 的時候賣股票，淨利 3
第 2 次買賣：在股票價格是 2 的時候買股票，現在還不能賣股票
--end for--
cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
x: 7 P: [1, -1] B: [6, 3]
現在要決定，最多只能做 1 次買賣的話，買賣股票的時機
結果：在股票價格是 1 的時候買股票，在股票價格是 7 的時候賣股票，淨利 6
--begin for--
i: 1 P: [1, -1] B: [6, 8]
現在要決定，最多只能做 2 次買賣的話，2 次買賣股票的時機
P[1] 算出來是 -1：現在買股票太貴了，不買。所以維持原狀是 -1
第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 4 的時候賣股票，淨利 3
第 2 次買賣：在股票價格是 2 的時候買股票，在股票價格是 7 的時候賣股票，淨利 5
--end for--
cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
x: 2 P: [1, -1] B: [6, 8]
現在要決定，最多只能做 1 次買賣的話，買賣股票的時機
結果：維持原狀，在股票價格是 1 的時候買股票，在股票價格是 7 的時候賣股票，淨利 6
--begin for--
i: 1 P: [1, -4] B: [6, 8]
現在要決定，最多只能做 2 次買賣的話，2 次買賣股票的時機
P[1] 是 -4：若比照 B[0] 的時機交易後獲得淨利 6，然後在現在股票價格 2 的時候買股票，會倒賺 4 塊
已經準備要改成：第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 7 的時候賣股票
第 2 次買賣：在股票價格是 2 的時候買股票，現在還不能賣股票
但是，若比照上述方式進行買賣，現在卻還不能賣股票，淨利比不上原本的方式，所以先維持原狀：
第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 4 的時候賣股票，淨利 3
第 2 次買賣：在股票價格是 2 的時候買股票，在股票價格是 7 的時候賣股票，淨利 5
--end for--
cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
x: 9 P: [1, -4] B: [8, 8]
現在要決定，最多只能做 1 次買賣的話，買賣股票的時機
結果：在股票價格是 1 的時候買股票，在股票價格是 9 的時候賣股票，淨利 8
--begin for--
i: 1 P: [1, -4] B: [8, 13]
現在要決定，最多只能做 2 次買賣的話，2 次買賣股票的時機
P[1]：現在買股票太貴了，不買。所以維持原狀是 -4
第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 7 的時候賣股票，淨利 6
第 2 次買賣：在股票價格是 2 的時候買股票，在股票價格是 9 的時候賣股票，淨利 7
--end for--
cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
x: 0 P: [0, -4] B: [8, 13]
現在要決定，最多只能做 1 次買賣的話，買賣股票的時機
P[0] 是 0：發現更低的股票購買價格，先筆記下來。
如果日後找到淨利更好的賣股票時機，就會改成在股票價格是 0 的時候買股票。
結果：先維持原狀，在股票價格是 1 的時候買股票，在股票價格是 9 的時候賣股票，淨利 8
--begin for--
i: 1 P: [0, -8] B: [8, 13]
現在要決定，最多只能做 2 次買賣的話，2 次買賣股票的時機
P[1] 是 -8：若比照 B[0] 的時機交易後獲得淨利 8，然後在現在股票價格 0 的時候買股票，會倒賺 8 塊
已經準備要改成：第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 9 的時候賣股票
第 2 次買賣：在股票價格是 0 的時候買股票，現在還不能賣股票
但是，若比照上述方式進行買賣，現在卻還不能賣股票，淨利比不上原本的方式，所以先維持原狀：
第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 7 的時候賣股票，淨利 6
第 2 次買賣：在股票價格是 2 的時候買股票，在股票價格是 9 的時候賣股票，淨利 7
--end for--
cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
x: 9 P: [0, -8] B: [9, 13]
現在要決定，最多只能做 1 次買賣的話，買賣股票的時機
結果：在股票價格是 0 的時候買股票，在股票價格是 9 的時候賣股票，淨利 9
--begin for--
i: 1 P: [0, -8] B: [9, 17]
現在要決定，最多只能做 2 次買賣的話，2 次買賣股票的時機
P[1]：現在買股票太貴了，不買。所以維持原狀是 -8
第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 9 的時候賣股票，淨利 8
第 2 次買賣：在股票價格是 0 的時候買股票，在股票價格是 9 的時候賣股票，淨利 9
--end for--
Comments
Post a Comment