3573. Best Time to Buy and Sell Stock V

Description

You are given an integer array prices where prices[i] is the price of a stock in dollars on the ith day, and an integer k.

You are allowed to make at most k transactions, where each transaction can be either of the following:

• Normal transaction: Buy on day i, then sell on a later day j where i < j. You profit prices[j] - prices[i].

• Short selling transaction: Sell on day i, then buy back on a later day j where i < j. You profit prices[i] - prices[j].

Note that you must complete each transaction before starting another. Additionally, you can't buy or sell on the same day you are selling or buying back as part of a previous transaction.

Return the maximum total profit you can earn by making at most k transactions.

 

Example 1:

Input: prices = [1,7,9,8,2], k = 2

Output: 14

Explanation:

We can make $14 of profit through 2 transactions:

• A normal transaction: buy the stock on day 0 for $1 then sell it on day 2 for $9.
• A short selling transaction: sell the stock on day 3 for $8 then buy back on day 4 for $2.

Example 2:

Input: prices = [12,16,19,19,8,1,19,13,9], k = 3

Output: 36

Explanation:

We can make $36 of profit through 3 transactions:

• A normal transaction: buy the stock on day 0 for $12 then sell it on day 2 for $19.
• A short selling transaction: sell the stock on day 3 for $19 then buy back on day 4 for $8.
• A normal transaction: buy the stock on day 5 for $1 then sell it on day 6 for $19.

 

Constraints:

• 2 <= prices.length <= 103
• 1 <= prices[i] <= 109
• 1 <= k <= prices.length / 2

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(nk)
• Space complexity: O(nk)

 

JavaScript

/**
 * @param {number[]} prices
 * @param {number} k
 * @return {number}
 */
const maximumProfit = function (prices, k) {
  const n = prices.length;
  const SKIP = 0;
  const NORMAL = 1;
  const SHORT_SELLING = 2;
  const dp = Array.from({ length: n }, () => {
    return new Array(k + 1)
      .fill('')
      .map(() => new Array(3).fill(-1));
  });

  const transactionStock = (index, times, state) => {
    if (!times) return 0;

    const price = prices[index];

    if (!index) {
      if (state === SKIP) return 0;

      return state === NORMAL ? -price : price;
    }

    if (dp[index][times][state] > -1) return dp[index][times][state];

    let result = transactionStock(index - 1, times, state);

    if (state === SKIP) {
      const normalProfit = transactionStock(index - 1, times, NORMAL) + price;
      const shortSellingProfit = transactionStock(index - 1, times, SHORT_SELLING) - price;

      result = Math.max(normalProfit, shortSellingProfit, result);
    } else if (state === NORMAL) {
      const profit = transactionStock(index - 1, times - 1, SKIP) - price;

      result = Math.max(profit, result);
    } else {
      const profit = transactionStock(index - 1, times - 1, SKIP) + price;

      result = Math.max(profit, result);
    }

    dp[index][times][state] = result;

    return result;
  };

  return transactionStock(n - 1, k, SKIP);
};