2021-07-07：股票问题4。给定一个整数数组 prices ，它的第 i 个元素 pricesi 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
福大大 答案2021-07-07：
动态规划。
时间复杂度：O(NK)。空间复杂度：O(NK)。
代码用golang编写。代码如下：
代码语言：txt复制package main
import "fmt"
func main() {
k := 2
prices := []int{3, 2, 6, 5, 0, 3}
ret := maxProfit(k, prices)
fmt.Println(ret)
}
func maxProfit(K int, prices []int) int {
if len(prices) == 0 {
return 0
}
N := len(prices)
if K >= N/2 {
return allTrans(prices)
}
dp := make([][]int, K 1)
for i := 0; i < K 1; i {
dp[i] = make([]int, N)
}
ans := 0
for tran := 1; tran <= K; tran {
pre := dp[tran][0]
best := pre - prices[0]
for index := 1; index < N; index {
pre = dp[tran-1][index]
dp[tran][index] = getMax(dp[tran][index-1], prices[index] best)
best = getMax(best, pre-prices[index])
ans = getMax(dp[tran][index], ans)
}
}
return ans
}
func allTrans(prices []int) int {
ans := 0
for i := 1; i < len(prices); i {
ans = getMax(prices[i]-prices[i-1], 0)
}
return ans
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}执行结果如下：
图片左神java代码
