2021-07-08：股票问题5。给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
福大大 答案2021-07-08：
空间压缩的动态规划。
时间复杂度：O(N)。空间复杂度：O(1)。
代码用golang编写。代码如下：
代码语言：txt复制package main
import "fmt"
func main() {
arr := []int{1, 2, 3, 4, 1, 6, 7}
ret := maxProfit(arr)
fmt.Println(ret)
}
func maxProfit(prices []int) int {
if len(prices) < 2 {
return 0
}
buy1 := getMax(-prices[0], -prices[1])
sell1 := getMax(0, prices[1]-prices[0])
sell2 := 0
for i := 2; i < len(prices); i {
tmp := sell1
sell1 = getMax(sell1, buy1 prices[i])
buy1 = getMax(buy1, sell2-prices[i])
sell2 = tmp
}
return sell1
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}执行结果如下：
图片左神java代码
