188-best-time-to-buy-and-sell-stock-iv.js

/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = function(k, prices) {
  if (!prices.length) return 0
  let len = prices.length,
    res = 0
  if (k >= ~~(len / 2)) {
    for (let i = 1; i < len; i++) {
      res += Math.max(prices[i] - prices[i - 1], 0)
    }
    return res
  }
  const buy = new Array(k + 1).fill(Number.MIN_SAFE_INTEGER)
  const sell = new Array(k + 1).fill(0)

  for (let p of prices) {
    for (let i = 1; i <= k; i++) {
      buy[i] = Math.max(sell[i - 1] - p, buy[i])
      sell[i] = Math.max(buy[i] + p, sell[i])
    }
  }
  return sell[k]
}

// another

/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = function(k, prices) {
    if(prices.length === 0) return 0
    
    if(k > (prices.length/2)) {
        let profit = 0
        for(let i = 1; i < prices.length; i++) {
            if(prices[i] > prices[i-1]) profit += prices[i] - prices[i-1]
        }
        return profit
    } else {
        let dp = new Array(prices.length).fill(0)
        let length = prices.length
        for(let j = 0; j < k; j++) {
            let min = prices[0], max = 0
            for(let i = 0; i < length; i++) {
                min = Math.min(min, prices[i] - dp[i])
                max = Math.max(max, prices[i] - min)
                dp[i] = max
            }
        }
        return dp.pop()
    }
}

 // another

/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = function(k, prices) {
  if (k >= prices.length / 2) {
    let max = 0;
    for(let i = 1; i < prices.length; i++) {
      if (prices[i] > prices[i - 1]) {
        max += prices[i] - prices[i - 1];
      }
    }
    return max;
  }
  if (prices.length === 0) return 0;
  let dp = new Array(k + 1);
  dp[0] = new Array(prices.length).fill(0);
  for (let t = 1; t <= k; t++) {
    dp[t] = [0];
    let max = dp[t - 1][0] - prices[0];
    for (let day = 1; day < prices.length; day++) {
      dp[t][day] = Math.max(dp[t][day - 1], max + prices[day]);
      max = Math.max(max, dp[t - 1][day] - prices[day]);
    }
  }
  return dp[k][prices.length - 1];
}