Skip to content

3892. Best Time To Buy And Sell Stock V

3892. Best Time to Buy and Sell Stock V

Medium

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

Solution

class Solution {
    private long dp[][][][];
    public long maximumProfit(int[] prices, int k) {
        int n = prices.length;
        dp = new long[n + 1][2][2][k + 1];
        for (long current[][][] : dp) for (long current1[][] : current) for (long current2[] : current1) Arrays.fill(current2, -1);
        long res = solve(0, 0, 0, k, prices);
        return res;
    }
    private long solve(int ind, int hasBought, int hasSold, int Rem, int prices[]) {
        if (ind == prices.length - 1) {
            if (hasBought == 1) return prices[ind];
            else if (hasSold == 1) return -prices[ind];
            return 0;
        }
        if (ind >= prices.length || Rem <= 0) return 0;
        if (dp[ind][hasBought][hasSold][Rem] != -1) return dp[ind][hasBought][hasSold][Rem];
        if (hasBought == 0 && hasSold == 0) {
            long op1 = 0, op2 = 0, op3 = 0;
            op1 = -prices[ind] + solve(ind + 1, 1, 0, Rem, prices);
            op2 = prices[ind] + solve(ind + 1, 0, 1, Rem, prices);
            op3 = solve(ind + 1, 0, 0, Rem, prices);
            return dp[ind][hasBought][hasSold][Rem] = Math.max(op1, Math.max(op2, op3));
        }
        else if (hasBought == 1 && hasSold == 0) {
            long op1 = 0, op2 = 0;
            op1 = prices[ind] + solve(ind + 1, 0, 0, Rem - 1, prices);
            op2 = solve(ind + 1, hasBought, hasSold, Rem, prices);
            return dp[ind][hasBought][hasSold][Rem] = Math.max(op1, op2);
        }
        else if (hasBought == 0 && hasSold == 1) {
            long op1 = 0, op2 = 0;
            op1 = -prices[ind] + solve(ind + 1, 0, 0, Rem - 1, prices);
            op2 = solve(ind + 1, hasBought, hasSold, Rem, prices);
            return dp[ind][hasBought][hasSold][Rem] = Math.max(op1, op2);
        }
        return 0;
    }
}

Complexity Analysis

  • Time Complexity: O(?)
  • Space Complexity: O(?)

Explanation

[Add detailed explanation here]