The Best Time to Buy and Sell Stocks with Commission#

Given an integer array prices, where the i-th element represents the stock price on the i-th day; non-negative integer fee represents the transaction commission for trading stocks.
You can complete transactions unlimited times, but you need to pay commission for each transaction. If you have already bought a stock, you cannot buy another stock before selling it.
Return the maximum profit obtained.
Note: A transaction here refers to the entire process of buying, holding, and selling stocks. You only need to pay a commission once for each transaction.

Example#

Solution#

/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
    const n = prices.length;
    const dp = new Array(2).fill(0).map(v => new Array(n).fill(0));
    dp[0][0] = -prices[0];
    dp[1][0] = 0;
    for (let i = 1; i < n; ++i) {
        // The final state at this point is holding: continue holding / not holding, buy
        dp[0][i] = Math.max(dp[0][i - 1], dp[1][i - 1] - prices[i]);
        // The final state at this point is not holding: continue not holding / sell holding
        dp[1][i] = Math.max(dp[1][i - 1], dp[0][i - 1] + prices[i] - fee);
    }
    return dp[1][n - 1];
};

Idea#

In a dynamic programming manner, a table can be printed based on the example in the problem statement.

It needs to be explained that at the end of each day's trading, there can only be two situations: holding one stock or not holding any stocks. Therefore, we assign two states to it. The first state is holding, which represents the maximum profit of holding one stock at the end of the i-th day's trading. The second state is not holding, which represents the maximum profit of not holding any stock at the end of the i-th day's trading. By considering the transition of dp[0][i], the possible transition states are that holding one stock from the previous day, i.e. dp[1][i-1], or not having any stock at the end of the previous day, i.e. dp[1][i-1]. In this case, we need to buy it and subtract prices[i] to gain profit. The transition formula can be listed as dp[1][i] = max{dp[1][i-1], dp[0][i-1] - prices[i]}. Similarly, when considering the transition formula for dp[1][i], if there is no stock at the end of the day, the possible transition state is that there is no stock at the end of the previous day, i.e. dp[1][i-1], or holding one stock at the end of the previous day, i.e. dp[0][i-1]. In this case, we need to sell it and gain prices[i] of profit, but we need to pay the fee of transaction. Therefore, to maximize the profit, the transition formula is listed as dp[0][i] = max{dp[0][i-1], dp[1][i-1] + prices[i] - fee}. For all the initialization states, according to the state definition, we know that the profit is dp[0][0]=0 at the end of the 0-th day's trading, and dp[1][0]=−prices[0]. Afterwards, as long as we calculate the state one by one from the front to the end, we can get the final result.

First, define n as the length of the array, and then directly generate a 2 * n array using the constructor and fill it with 0. The reason for filling the outer array with 0 is that the map will skip empty array slots. In fact, any value can be filled in the outer array, since the return value of the map callback function will overwrite it. Then, define the values of the first column as the initialization. Afterwards, define a loop to build the list. Specific rules can refer to the table explanation above. Then return the last value of the second row.

Daily Question#

Reference#