SOURCE

//
// price[i], K笔交易，求最大获利
//

function maxProfit(prices, K) {
    let profit = new Array(prices.length) // profit[i][k][0] 第i天、k次交易、不持有股票
    

    for(let i in prices) {
        profit[i] = new Array(K+1)
        for(let k = 0; k <= K; k++) {
            profit[i][k] = new Array(2);
            if(k == 0) {
                profit[i][0][0] = 0
                profit[i][0][1] = -100000
            } else {
                if (i > 0) {
                    profit[i][k][0] = Math.max(profit[i-1][k][1]+prices[i], profit[i-1][k][0])
                    profit[i][k][1] = Math.max(profit[i-1][k][1], profit[i-1][k-1][0]-prices[i])
                } else {
                    profit[i][k][0] = 0
                    profit[i][k][1] = -prices[i]
                }
            }
        }
        
    }
    console.log(profit);

    return profit[prices.length - 1][K][0];
}

let profit = maxProfit([5, 4, 7, 10, 8, 11, 15, 10, 11], 2)
console.log(profit);

//
// price[i], 1笔交易，求最大获利
//

function maxProfit_1(prices) {
    let profit = new Array(prices.length) // profit[i][k][0] 第i天、k次交易、不持有股票
    

    for(let i in prices) {
        profit[i] = new Array(2)
        if(i == 0) {
            profit[i][0] = 0
            profit[i][1] = -prices[i]
        } else {
            profit[i][0] = Math.max(profit[i-1][0], profit[i-1][1] + prices[i])
            profit[i][1] = Math.max(profit[i-1][1], - prices[i])
        }
    }
    console.log(profit);

    return profit[prices.length - 1][0];
}

let profit1 = maxProfit_1([5, 4, 7, 10, 8, 11, 15, 10, 11])
console.log(profit1);


//
// price[i], 无限次笔交易，求最大获利
//

function maxProfit_inf(prices) {
    let profit = new Array(prices.length) // profit[i][k][0] 第i天、k次交易、不持有股票
    

    for(let i in prices) {
        profit[i] = new Array(2)
        if(i == 0) {
            profit[i][0] = 0
            profit[i][1] = - prices[i]
        } else {
            profit[i][0] = Math.max(profit[i-1][0], profit[i-1][1] + prices[i])
            profit[i][1] = Math.max(profit[i-1][1], profit[i-1][0] - prices[i])
        }
    }
    console.log(profit);

    return profit[prices.length - 1][0];
}

let profit_inf = maxProfit_inf([5, 4, 7, 10, 8, 11, 15, 10, 11])
console.log(profit_inf);


//
// price[i], 2笔交易，求最大获利
//

function maxProfit2(prices) {
    let profit = new Array(prices.length) // profit[i][k][0] 第i天、k次交易、不持有股票
    

    for(let i in prices) {
        profit[i] = new Array(3)
        for(let k = 0; k <= 2; k ++ ) {
            profit[i][k] = new Array(2)
            if(k == 0) {
                profit[i][0][0] = 0
                profit[i][0][1] = -100000
            } else if (k == 1) {
                if(i == 0) {
                    profit[0][1][0] = -100000
                    profit[0][1][1] = -prices[0]
                } else {
                    profit[i][k][0] = Math.max(profit[i-1][k][0], profit[i-1][k][1] + prices[i])
                    profit[i][k][1] = Math.max(profit[i-1][k][1], profit[i-1][k-1][0] - prices[i])
                }
            } else {
                if(i == 0) {
                    profit[0][2][0] = -100000
                    profit[0][2][1] = - 100000
                } else {
                    profit[i][k][0] = Math.max(profit[i-1][k][0], profit[i-1][k][1] + prices[i])
                    profit[i][k][1] = Math.max(profit[i-1][k][1], profit[i-1][k-1][0] - prices[i])
                }
            }
        }
    }
    console.log(profit);

    return profit[prices.length - 1][2][0];
}

let profit2 = maxProfit2([5, 4, 7, 10, 8, 11, 15, 10, 11])
console.log(profit2);