未分類

Best Time to Buy and Sell Stock with Cooldown

DynamicProgramming, Go, LeetCode

Best Time to Buy and Sell Stock with Cooldown

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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

  • You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
  • After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

For example:

1
2
3
prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]
提示 解題應用
DynamicProgramming 規律觀查

Default:

1
2
3
func maxProfit(prices []int) int {
}

解答思路:

雖然先前有一篇非常類似的Best Time to Buy and Sell Stock II，但是多了需要冷卻的時間(賣完股票強制休1天才能再買)，整個思考方式就會完全不一樣，最主要是會變成以手上是否有股票為主，在今天交易結束後如果手上持有股票，表示有兩種可能的情況，一種是前天(或更早)手上就沒有股票到了今天交易才買，另一種是昨天手上就持有股票到了今天還是仍沒有任何交易的動作，反之如果在今天交易結束後手上並未持有股票，則一樣表示有兩種可能的情況，一種是昨天(或更早)手上就持有股票到了今天交易才賣，另一種是昨天手上就未持有股票到了今天還是仍沒有任何交易的動作，總而言之每天就是分別統計持有股票與否各別的兩種情況取最大值，購買股票就累加負數的價格，販賣股票則累加正數的價格，最後整個交易結束手上未持有股票的獲利就會是最大值。

程式碼解說:

先判斷每日股票票價的陣列是否為空，如果是便直接回傳0，而如思路所述需要分別統計持有股票與否各別的兩種情況取最大值，所以第一天先為持有股票的情況購買(累加負數的價格)做為初始化，接著才開始從第二天統計，而每天交易之前先紀錄下前一次(昨天)的交易結果，先針對交易結束後手上持有股票的情況取最大值，一種是前天手上就沒有股票(preNoStock當下取出的紀錄是前一輪迴圈的統計，也就是昨天的昨天沒有股票的情況)到了今天交易才買，另一種是昨天手上就持有股票到了今天還是仍沒有任何交易的動作，再來則是對交易結束後手上並未持有股票的情況取最大值，一種是昨天(preOwnStock當下取出的紀錄是同一輪迴圈的統計，正好就是昨天的情況)手上就持有股票到了今天交易才賣(累加正數的價格)，另一種是昨天手上就未持有股票到了今天還是仍沒有任何交易的動作，最後整個交易結束手上未持有股票的獲利就會是最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}
	var noStock int
	var preNoStock int
	var preOwnStock int
	ownStock := -prices[0]
	for _, v := range prices[1:] {
		preOwnStock = ownStock
		ownStock = max(preNoStock-v, preOwnStock)
		preNoStock = noStock
		noStock = max(preOwnStock+v, preNoStock)
	}
	return noStock
}

這部分就只是單純比較兩個值的大小，並回傳較大的值

1
2
3
4
5
6
func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}
	var noStock int
	var preNoStock int
	var preOwnStock int
	ownStock := -prices[0]
	for _, v := range prices[1:] {
		preOwnStock = ownStock
		ownStock = max(preNoStock-v, preOwnStock)
		preNoStock = noStock
		noStock = max(preOwnStock+v, preNoStock)
	}
	return noStock
}
func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

總結:

給予一段每日股票票價的陣列，要求找出能賺取的最大利潤，每天只能選擇購買或販售且賣完股票強制休1天才能再買，最主要是會以思考手上是否有股票為主，在今天交易結束後如果手上持有股票，表示有兩種可能的情況，一種是前天(或更早)手上就沒有股票到了今天交易才買，另一種是昨天手上就持有股票到了今天還是仍沒有任何交易的動作，反之如果在今天交易結束後手上並未持有股票，則一樣表示有兩種可能的情況，一種是昨天(或更早)手上就持有股票到了今天交易才賣，另一種是昨天手上就未持有股票到了今天還是仍沒有任何交易的動作，總而言之每天就是分別統計持有股票與否各別的兩種情況取最大值，購買股票就累加負數的價格，販賣股票則累加正數的價格，最後整個交易結束手上未持有股票的獲利就會是最大值。

分享到