Leetcode Link

Concept

Every day, we have two choices: either hold a stock or sell a stock.

Holding a stock means we either bought it on a previous day or purchased it today.
Selling a stock means we either still have cash from previous transactions or we sold a stock today.
To solve this problem efficiently, we can use dynamic programming.

Understanding the Problem

Given an array prices where prices[i] represents the stock price on the ith day, and an integer fee representing the transaction fee, our goal is to determine the maximum profit achievable through multiple transactions while ensuring that we pay the fee each time we sell a stock.

prices = [1,3,2,8,4,9], fee = 2

Initial Approach

At first, we might attempt to define dp[i] as follows:

  • Buying a stock: dp[i] = dp[i-1] - prices[i]

  • Selling a stock: dp[i] = dp[i-1] + prices[i] - fee

  • Doing nothing: dp[i] = dp[i-1]
    However, this approach is incorrect because in order to sell a stock, we must have previously purchased and held it. This means we need to track two separate states:

  • hold[i] – The maximum profit when holding a stock on day i

  • cash[i] – The maximum profit when not holding any stock (i.e., holding cash) on day i

State Transition Equations

Since we can either continue holding or buy a new stock, the state transitions are as follows:

  • Buying a stock:
    hold[i] = max(hold[i-1], cash[i-1] - prices[i])
    (Either we continue holding from the previous day, or we buy a new stock using available cash.)
    Selling a stock:
  • cash[i] = max(cash[i-1], hold[i-1] + prices[i] - fee)
    (Either we keep the cash from yesterday, or we sell the stock we were holding and gain profit minus the transaction fee.)
  • Doing nothing:
    • hold[i] = hold[i-1] (If we don’t buy today, our hold value remains the same.)
    • cash[i] = cash[i-1] (If we don’t sell today, our cash remains the same.)

Implementation

We create two arrays, hold and cash, to store the values for each state over n days:

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int [] hold = new int[n];
        int [] cash = new int[n];

        hold[0] = -prices[0];
        cash[0] = 0;

        for (int i = 1; i < n; i++) {
            hold[i] = Math.max(hold[i-1], cash[i-1] - prices[i]);
            cash[i] = Math.max(cash[i-1], hold[i-1] + prices[i] - fee);
        }
        return cash[n-1];
        
    }
}