买卖股票专题系列4---买卖股票的最佳时机4

题目：

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

题解：

　　该题是买卖股票3的升级版本，假若理解了买卖股票3的解法，那么此题稍加改动即可解出。话不多说，下面直接上代码：

Java版本：

public int maxProfit(int k, int[] prices) {
        if(prices == null || prices.length < 2) return 0;
        int n = prices.length;//n天
        k = Math.min(k,n/2);//n天最多进行n/2笔交易
        //用两个记忆数组分别记录买入、卖出的状态
        int[][] hold = new int[n][k+1];//hodl[i][j] 第i天持有股票且交易j次
        int[][] notHold = new int[n][k+1];//notHold[i][j] 第i天不持有股票且交易j次
        //初始化 第1天持有股票/不持有股票且交易j次的利润  
        hold[0][0] = -prices[0];
        notHold[0][0] = 0;
        for(int i=1;i<=k;i++){
            hold[0][i] = notHold[0][i] = Integer.MIN_VALUE / 2;//不持有股票
        }

        //未持股时利润才最大
        for(int i=1;i<prices.length;i++){
            hold[i][0] = Math.max(hold[i - 1][0], notHold[i - 1][0] - prices[i]);
            for(int j=1;j<=k;j++){
                hold[i][j] = Math.max(hold[i-1][j], notHold[i-1][j] - prices[i]);
                notHold[i][j] = Math.max(notHold[i-1][j], hold[i-1][j-1] + prices[i]);
            }
        }
        int max = 0;
        for(int i=0;i<=k;i++){
            max = Math.max(notHold[n-1][i],max);
        }
        return max;
    }

JS版本：

var maxProfit = function(k, prices) {
    if(prices == null || prices.length <2) return 0;
    let n = prices.length;
    //二维记忆数组
    let hold = [];//持有股票 hold[i][j] 第i天持有股票且交易j次
    let notHold = [];//未持有股票 第i天不持有股票且交易j次
    k = Math.min(k,Math.floor(n/2));////最多进行n/2次交易
    //初始化
    for(let i=0;i<n;i++){
        hold[i] = Array(k+1).fill(0),notHold[i] = Array(k+1).fill(0);
    }
    hold[0][0] = -prices[0];
    notHold[0][0] = 0;
    for(let i=1;i<=k;i++){
        hold[0][i] = notHold[0][i] = -Infinity;
    }

    for(let i=1;i<n;i++){
        hold[i][0] = Math.max(hold[i-1][0], notHold[i-1][0] - prices[i]);
        for(let j=1;j<=k;j++){
            hold[i][j] = Math.max(hold[i-1][j], notHold[i-1][j] - prices[i]);
            notHold[i][j] = Math.max(notHold[i-1][j], hold[i-1][j-1] + prices[i]);
        }
    }

    let max = 0;
    for(let i=0;i<=k;i++){
        max = Math.max(max,notHold[n-1][i]);
    }

    return max;
};