2021-07-07：股票问题4。给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成

2021-07-07：股票问题4。给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

福大大 答案2021-07-07：

动态规划。
时间复杂度：O(NK)。空间复杂度：O(NK)。

代码用golang编写。代码如下：

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代码

2021-07-07：股票问题4。给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成的相关教程结束。