未分類

Best Time to Buy and Sell Stock II

Array, Go, Greedy, LeetCode

Best Time to Buy and Sell Stock II

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). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

提示 解題應用
Array Array/Slice
Greedy 規律觀查

Default:

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

解答思路:

建議可以先參考先前Best Time to Buy and Sell Stock的解法，解說較為詳細，基本上概念完全一樣，只是將先前題的程式碼稍做修改而已，如果能找出最好的一筆利潤，當然這次能允許多筆交易的情況下要找出最大利潤就不會太困難。

變成要在多筆交易的情況下找出最大利潤其實透過觀查就會發現到一件事情，如果先前找出最好的一筆交易期間，在相同的時間內改成多筆交易的話利潤一定會比先前的一筆最佳交易更優(在不會笨到賠錢賣的運作下，最差的情況頂多與一筆交易的利潤相同)，所以只要有能賺取利潤的機會就只要馬上賣出，如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
            最好的一筆交易
  | - - - - - - - - - - - - - - - |
最低價                            最高價
  1                               100
  
利潤: 100 - 1 = 99
              多筆交易(1)
  | - - - - - - - | - - - - - - - |
最低價     (    賣出/買入   )      最高價
  1               50              100
  
利潤: (50-1) + (100-50) = 99
              多筆交易(2)
  | - - - | - - - | - - - | - - - |
最低價     (    賣出/買入   )      最高價
  1       99      2       99      100
  
利潤: (99-1) + (99-2) + (100-99) = 196

最後再注意到同一天可以在賣出股票之後當場再買入股票，好比多筆交易(2)的第四天在以99元賣出之後，馬上又買了99元的股票再第五天才賣出就能多賺1元。

程式碼解說:

因為在相同的時間內多筆交易利潤一定會比先前的一筆最佳交易更優，所以只是將先前的邏輯改成只要有能賺取利潤的機會就馬上賣出，這邊只會針對與先前不同的部分來解說，最主要就是當發現賣價比買價高能賺取利潤的時候，就將股票賣出(先前還會多判斷是否比目前的最大利潤大)，並從原本的取代最大利潤改為將每次得到的利潤做總合，最後同一天可以在賣出股票之後當場再買入股票，因此在賣出之後要記得馬上將買入股票的價格改成今日的價格

1
2
3
4
if buyPrice < sellPrice {
	maxProfit += sellPrice - buyPrice
	buyPrice = v
}

完整程式碼:

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 maxProfit int
	buyPrice := prices[0]
	sellPrice := prices[0]
	for _, v := range prices[1:] {
		if v < buyPrice {
			buyPrice = v
			sellPrice = 0
		}
		if v > sellPrice {
			sellPrice = v
			if buyPrice < sellPrice {
				maxProfit += sellPrice - buyPrice
				buyPrice = v
			}
		}
	}
	return maxProfit
}

總結:

建議可以先參考先前Best Time to Buy and Sell Stock的解法，解說較為詳細，基本上概念完全一樣，只是這次在允許多筆交易的情況下要找出最大利潤，透過觀查就會發現到如果先前找出最好的一筆交易期間，在相同的時間內改成多筆交易的話利潤一定會比先前的一筆最佳交易更優(最差的情況頂多相同)，所以只是將先前的邏輯改成只要有能賺取利潤的機會就馬上賣出即可。

分享到