@toc
題目
Say you have an array for which the i-th 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.
給出一組股票價(jià)格 prices 和交易次數(shù) k轮洋，求出能獲取的最大收益被廓。
PS：持有股票時(shí)不能購買，需賣出才可再購買阱驾。
解題思路
基于 k 和 prices 數(shù)量的關(guān)系分為兩種情況：
-
k >= prices.count / 2時(shí)，由于一次交易需要占用兩天時(shí)間吊趾，所以此時(shí)所有漲幅均可交易彩库，將所有漲幅進(jìn)行加和即可。(if (prices[i] > prices[i-1]) {res += prices[i] - prices[i-1]}) -
k < prices.count / 2時(shí)槽惫，則prices.count / 2次交易可能并未取滿周叮，可采用動(dòng)態(tài)規(guī)劃，mp[j][i]為j天進(jìn)行i次交易時(shí)獲得的最大收益-
mp[j][i]的值分為兩種情況- 第
j天沒有進(jìn)行交易界斜，則值與mp[j-1][i]相同 - 在前
j-1天進(jìn)行了i-1次交易仿耽，且在前j-1天中某一天進(jìn)行了買入操作,第j天以prices[j]的價(jià)格賣出，
- 第
- 兩種情況取較大值賦予
mp[j][i]
-
代碼實(shí)現(xiàn)
Runtime: 28 ms
Memory: 20.9 MB
func maxProfit(_ k: Int, _ prices: [Int]) -> Int {
// 過濾無法買賣的情況
guard prices.count > 1, k > 0 else { return 0 }
// 價(jià)格走勢的天數(shù) priceLen
let priceLen = prices.count
// 當(dāng)交易次數(shù) k 大于 priceLen 的一半時(shí)各薇，則每次有漲幅的時(shí)候（if (prices[i] > prices[i-1]) ）都進(jìn)行交易
if k >= (priceLen / 2) {
var res = 0
for i in 1..<priceLen {
if (prices[i] > prices[i-1]) {
res += prices[i] - prices[i-1]
}
}
// 返回結(jié)果
return res
}
// 若 k 小于 priceLen 的一半项贺，則需要篩選獲利最高的 k 次交易
// mp[j][i] 為 j 天進(jìn)行 i 次交易時(shí)獲得的最大收益
var mp = [[Int]](repeating: [Int](repeating: 0, count: k + 1), count: prices.count)
// 遍歷 i 次交易
for i in 1...k {
// localMax 實(shí)際為 mp[i - 1][0] - prices[0]，
// 由于 mp[i - 1][0] 表示 0 天峭判，所以數(shù)值始終未 0 开缎，可以簡寫成 localMax = -prices[0]
// localMax 表示 j 天進(jìn)行 i-1 次操作后，再以 prices[j] 買入時(shí)的最大收益標(biāo)識(shí)
var localMax = -prices[0]
//遍歷 j 天
for j in 1..<priceLen {
// mp[j][i] 表示 j 天進(jìn)行 i 次交易時(shí)獲得的最大收益林螃，分兩種計(jì)算情況
// 1. 第 j 天沒有進(jìn)行交易奕删，則值與 mp[j-1][i] 相同
// 2. 在前 j-1 天進(jìn)行了 i-1 次交易，且在前 j-1 天中某一天進(jìn)行了買入操作,第 j 天以 prices[j] 的價(jià)格賣出(prices[j]+localMax)
// 兩種情況取較大值賦予 mp[j][i]
mp[j][i] = max(mp[j-1][i], prices[j]+localMax)
// 不斷更新 localMax
// j-1 天進(jìn)行 i-1 次交易治宣，并在第 j 天買入的收益（mp[j-1][i-1]-prices[j]）急侥，與當(dāng)前的 localMax 比較取較大值
localMax = max(localMax, mp[j-1][i-1]-prices[j])
}
}
// 返回 最后一天為止，進(jìn)行 k 次交易的最大收益值
return mp[prices.count-1][k]
}
