题目

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

示例 1

输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

解题思路

这个题有个坑，当购买次数超过总天数的 1/2 时就相当于无限次购买，有可能会导致内存溢出，所以不考虑购买次数用贪心算法最好，同时如果 k 太大，可能运行时间很慢，这时候与随便交易等价，利用贪心算法，只要后面的价格高就可以买卖，这题就一把梭直接用 贪心算法+动态规划 暴力解出来。

代码

func maxProfit(k int, prices []int) int {
profit := 0
if k >= len(prices)/2 { //无限次交易，贪心算法
    for i := 0; i < len(prices)-1; i++ {
        if prices[i] < prices[i+1] {
            profit += prices[i+1] - prices[i]
        }
    }
    return profit
}
//规定次数交易，动态规划
profit_0 := make([][]int, len(prices)) //不持有股票
profit_1 := make([][]int, len(prices)) //持有股票
//创建二维切片
for i := 0; i < len(prices); i++ {
    profit_0[i] = make([]int, k+1)
    profit_1[i] = make([]int, k+1)
}
//初始化第一天
for j := 0; j <= k; j++ {
    profit_1[0][j] = -prices[0]
}
//状态转移方程
for x := 1; x < len(prices); x++ { //遍历每天股票价格
    for y := 1; y < k+1; y++ { //遍历每次交易
        profit_0[x][y] = max(profit_0[x-1][y], profit_1[x-1][y]+prices[x])
        if profit < profit_0[x][y] {
            profit = profit_0[x][y]
        }
        profit_1[x][y] = max(profit_1[x-1][y], profit_0[x-1][y-1]-prices[x])
    }
}
return profit
}

func max(x int,y int) int{
    if x