3573. Best Time to Buy and Sell Stock V

Problem Link

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

Solution

---

C++

class Solution {
public:
    long long memo[1001][501][3];
 
    long long maximumProfit(vector<int>& prices, int k) {
        int N = prices.size();
        memset(memo, -1, sizeof(memo));
        return dp(0, k, 0, prices, N);
    }
 
    long long dp(int index, int k, int status, vector<int>& prices, int N) {
        if (index == N - 1) {
            if (status == 0) return 0;
            if (status == 1) return prices[index];
            return -prices[index];
        }
 
        if (k == 0) return 0;
 
        if (memo[index][k][status] != -1) return memo[index][k][status];
 
        // skip
        long long res = dp(index + 1, k, status, prices, N);
 
        if (status == 0) {
            // status == 1, long
            res = max(res, -prices[index] + dp(index + 1, k, 1, prices, N));
 
            // status == 2, short
            res = max(res, prices[index] + dp(index + 1, k, 2, prices, N));
        } else if (status == 1) {
            // sell now
            res = max(res, prices[index] + dp(index + 1, k - 1, 0, prices, N));
        } else {
            // buy back now
            res = max(res, -prices[index] + dp(index + 1, k - 1, 0, prices, N));
        }
 
        return memo[index][k][status] = res;
    }
};

Python3

class Solution:
    def maximumProfit(self, prices: List[int], k: int) -> int:
        N = len(prices)
        
        @cache
        def dp(index, currK, status):
            if index == N - 1:
                if status == 0: return 0
                if status == 1: return prices[index]
                return -prices[index]
 
            if index >= N or currK == 0: return 0
 
            # skip
            res = dp(index + 1, currK, status)
 
            if status == 0:
                # status == 1, long
                res = max(res, -prices[index] + dp(index + 1, currK, 1))
 
                # status == 2, short
                res = max(res, prices[index] + dp(index + 1, currK, 2))
            elif status == 1:
                # sell now
                res = max(res, prices[index] + dp(index + 1, currK - 1, 0))
            else:
                # buy back now
                res = max(res, -prices[index] + dp(index + 1, currK - 1, 0))
            
            return res
        
        ans = dp(0, k, 0)
        dp.cache_clear()
        return ans