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 i^th 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 <= 10³
1 <= prices[i] <= 10⁹
1 <= k <= prices.length / 2

Solutions

Solution 1: Dynamic Programming

We define $f[i][j][k]$ to represent the maximum profit on the first $i$ days, with at most $j$ transactions, and the current state $k$. Here, the state $k$ has three possibilities:

If $k = 0$, it means we do not hold any stock.
If $k = 1$, it means we are holding a stock.
If $k = 2$, it means we are holding a short position.

Initially, for any $j \in [1, k]$, we have $f[0][j][1] = -prices[0]$ and $f[0][j][2] = prices[0]$. This means buying a stock or opening a short position on day 0.

Next, we update $f[i][j][k]$ using state transitions. For each day $i$ and each transaction $j$, we update according to the current state $k$:

If $k = 0$, meaning no stock is held, this state can be reached from three situations:
- No stock was held the previous day.
- A stock was held the previous day and sold today.
- A short position was held the previous day and bought back today.
If $k = 1$, meaning a stock is held, this state can be reached from two situations:
- A stock was held the previous day.
- No stock was held the previous day and a stock is bought today.
If $k = 2$, meaning a short position is held, this state can be reached from two situations:
- A short position was held the previous day.
- No stock was held the previous day and a short position is opened (sold) today.

That is, for $1 \leq i < n$ and $1 \leq j \leq k$, we have the following state transition equations:

\[ \begin{aligned} f[i][j][0] &= \max(f[i - 1][j][0], f[i - 1][j][1] + prices[i], f[i - 1][j][2] - prices[i]) \\ f[i][j][1] &= \max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i]) \\ f[i][j][2] &= \max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i]) \end{aligned} \]

Finally, we return $f[n - 1][k][0]$, which is the maximum profit after at most $k$ transactions and not holding any stock at the end of $n$ days.

The time complexity is $O(n \times k)$, and the space complexity is $O(n \times k)$, where $n$ is the length of the array $\textit{prices}$ and $k$ is the maximum number of transactions.

Python3JavaC++GoTypeScriptRust

class Solution:
    def maximumProfit(self, prices: List[int], k: int) -> int:
        n = len(prices)
        f = [[[0] * 3 for _ in range(k + 1)] for _ in range(n)]
        for j in range(1, k + 1):
            f[0][j][1] = -prices[0]
            f[0][j][2] = prices[0]
        for i in range(1, n):
            for j in range(1, k + 1):
                f[i][j][0] = max(
                    f[i - 1][j][0],
                    f[i - 1][j][1] + prices[i],
                    f[i - 1][j][2] - prices[i],
                )
                f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i])
                f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i])
        return f[n - 1][k][0]

class Solution {
    public long maximumProfit(int[] prices, int k) {
        int n = prices.length;
        long[][][] f = new long[n][k + 1][3];
        for (int j = 1; j <= k; ++j) {
            f[0][j][1] = -prices[0];
            f[0][j][2] = prices[0];
        }
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= k; ++j) {
                f[i][j][0] = Math.max(f[i - 1][j][0],
                    Math.max(f[i - 1][j][1] + prices[i], f[i - 1][j][2] - prices[i]));
                f[i][j][1] = Math.max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i]);
                f[i][j][2] = Math.max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i]);
            }
        }
        return f[n - 1][k][0];
    }
}

class Solution {
public:
    long long maximumProfit(vector<int>& prices, int k) {
        int n = prices.size();
        long long f[n][k + 1][3];
        memset(f, 0, sizeof(f));
        for (int j = 1; j <= k; ++j) {
            f[0][j][1] = -prices[0];
            f[0][j][2] = prices[0];
        }

        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= k; ++j) {
                f[i][j][0] = max({f[i - 1][j][0], f[i - 1][j][1] + prices[i], f[i - 1][j][2] - prices[i]});
                f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i]);
                f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i]);
            }
        }

        return f[n - 1][k][0];
    }
};

func maximumProfit(prices []int, k int) int64 {
    n := len(prices)
    f := make([][][3]int, n)
    for i := range f {
        f[i] = make([][3]int, k+1)
    }

    for j := 1; j <= k; j++ {
        f[0][j][1] = -prices[0]
        f[0][j][2] = prices[0]
    }

    for i := 1; i < n; i++ {
        for j := 1; j <= k; j++ {
            f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1]+prices[i], f[i-1][j][2]-prices[i])
            f[i][j][1] = max(f[i-1][j][1], f[i-1][j-1][0]-prices[i])
            f[i][j][2] = max(f[i-1][j][2], f[i-1][j-1][0]+prices[i])
        }
    }

    return int64(f[n-1][k][0])
}

function maximumProfit(prices: number[], k: number): number {
    const n = prices.length;
    const f: number[][][] = Array.from({ length: n }, () =>
        Array.from({ length: k + 1 }, () => Array(3).fill(0)),
    );

    for (let j = 1; j <= k; ++j) {
        f[0][j][1] = -prices[0];
        f[0][j][2] = prices[0];
    }

    for (let i = 1; i < n; ++i) {
        for (let j = 1; j <= k; ++j) {
            f[i][j][0] = Math.max(
                f[i - 1][j][0],
                f[i - 1][j][1] + prices[i],
                f[i - 1][j][2] - prices[i],
            );
            f[i][j][1] = Math.max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i]);
            f[i][j][2] = Math.max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i]);
        }
    }

    return f[n - 1][k][0];
}

impl Solution {
    pub fn maximum_profit(prices: Vec<i32>, k: i32) -> i64 {
        let n = prices.len();
        let k = k as usize;
        let mut f = vec![vec![vec![0i64; 3]; k + 1]; n];
        for j in 1..=k {
            f[0][j][1] = -(prices[0] as i64);
            f[0][j][2] = prices[0] as i64;
        }
        for i in 1..n {
            for j in 1..=k {
                f[i][j][0] = f[i - 1][j][0]
                    .max(f[i - 1][j][1] + prices[i] as i64)
                    .max(f[i - 1][j][2] - prices[i] as i64);
                f[i][j][1] = f[i - 1][j][1].max(f[i - 1][j - 1][0] - prices[i] as i64);
                f[i][j][2] = f[i - 1][j][2].max(f[i - 1][j - 1][0] + prices[i] as i64);
            }
        }
        f[n - 1][k][0]
    }
}

3573. Best Time to Buy and Sell Stock V

Description

Solutions

Solution 1: Dynamic Programming

Comments