188. The best time to buy and sell stocks IV

Answer:

The question is similar to 123. The best time to buy and sell stocks III, except that the number of trades is changed to K twice. If you don’t have any ideas, you can look at problem 123.

  1. By the end of the firstiDay, the current has been traded2Each transaction can be bought (paid)prices[i]Or sell (revenue)prices[i]), so we can use length ask * 2 的dpArray recursion.
  2. Each trade should build on the previous one. For example, you can’t sell until you buy. Therefore, the state transition equation is:
// j is the index traversing dp
// 0~ I days, k trading status, each buy or sell, on the basis of the last trade
dp[j] = Math.max(
    dp[j], // The value ranges from 0 to i-1
    dp[j - 1] + (j & 1 ? price : -price), // Day I status
);
Copy the code
  1. sellkThe second profit is the most, so the maximum profit isdp[dp.length - 1].
/ * * *@param {number} k
 * @param {number[]} prices
 * @return {number}* /
var maxProfit = function (k, prices) {
  // A total of 2 trades can be made, each time there are two buy and sell states, so it needs to use k*2 state recursion
  let dp = new Array(k * 2);

  // Even positions are buys, and prices are priced for the first time [0]
  // The odd position is "sell", because no stock has been bought, can not sell, = 0
  for (let i = 0; i < dp.length; i++) {
    dp[i] = i & 1 ? 0 : -prices[0];
  }

  // Start from I =1 day, recurse daily transaction status
  for (let i = 1; i < prices.length; i++) {
    const price = prices[i]; // Cache the price of the day

    // 0~ I days, the optimal state of only 1 buy, the first transaction has no lead state
    dp[0] = Math.max(dp[0], -price);

    // 0~ I days, k trading status, each buy or sell, on the basis of the last trade
    for (let j = 1; j < dp.length; j++) {
      dp[j] = Math.max(
        dp[j], // The value ranges from 0 to i-1
        dp[j - 1] + (j & 1 ? price : -price), // Day I status); }}// The largest number of sales will result in the largest profit.
  // if k is 0, profit is 0
  return dp[dp.length - 1] | |0;
};
Copy the code