101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Dynamic Programming Approach - Complex approach
  2. State Machine Approach - Complex approach
  3. Greedy Approach - Complex approach

Approach 1: Dynamic Programming Approach

The key insight for solving this problem is to use dynamic programming to track the maximum profit in two states: holding a stock and not holding a stock.

Let's define two variables:

  • cash: the maximum profit we can have if we don't hold a stock at the end of day i.
  • hold: the maximum profit we can have if we hold a stock at the end of day i.

For each day, we have the following state transitions:

  • cash = max(cash, hold + prices[i] - fee): We either keep our cash from the previous day, or we sell the stock we're holding and pay the transaction fee.
  • hold = max(hold, cash - prices[i]): We either keep holding the stock from the previous day, or we buy a new stock using our cash.

At the end, the maximum profit will be in the cash state, as we want to end up without holding any stock.

Algorithm:

  1. Initialize cash = 0 (maximum profit with no stock) and hold = -prices[0] (maximum profit with a stock, which is negative because we spent money to buy it).
  2. Iterate through the prices array starting from the second day (i = 1):
  3. a. Calculate the new cash value: cash = max(cash, hold + prices[i] - fee).
  4. b. Calculate the new hold value: hold = max(hold, cash - prices[i]).
  5. Return cash as the maximum profit.

Time Complexity:

O(n)

Where n is the length of the prices array. We iterate through the array once, performing constant-time operations at each step.

Space Complexity:

O(1)

We only use a constant amount of extra space regardless of the input size.

Approach 2: State Machine Approach

Another way to think about this problem is as a state machine with two states: holding a stock and not holding a stock. We can transition between these states by buying or selling.

This approach is essentially the same as the dynamic programming approach, but it provides a different mental model for understanding the problem.

The key insight is that at each day, we want to maximize our profit in each state, and we can only transition between states by buying or selling.

Algorithm:

  1. Initialize s0 = 0 (maximum profit with no stock) and s1 = -prices[0] (maximum profit with a stock).
  2. Iterate through the prices array starting from the second day (i = 1):
  3. a. Calculate the new s0 value: s0 = max(s0, s1 + prices[i] - fee).
  4. b. Calculate the new s1 value: s1 = max(s1, s0 - prices[i]).
  5. Return s0 as the maximum profit.

Time Complexity:

O(n)

Where n is the length of the prices array. We iterate through the array once, performing constant-time operations at each step.

Space Complexity:

O(1)

We only use a constant amount of extra space regardless of the input size.

Approach 3: Greedy Approach

We can also solve this problem using a greedy approach by thinking about the problem in terms of buying at valleys and selling at peaks, while accounting for the transaction fee.

The key insight is that we want to buy at the lowest possible price and sell at the highest possible price, but we need to account for the transaction fee when deciding whether to sell.

We can keep track of the minimum buying price (adjusted for previous profits) and sell when the current price minus the fee is greater than this minimum buying price.

Algorithm:

  1. Initialize profit = 0 (total profit) and buyPrice = prices[0] (minimum buying price).
  2. Iterate through the prices array starting from the second day (i = 1):
  3. a. If prices[i] < buyPrice, update buyPrice = prices[i] (we found a lower buying price).
  4. b. Else if prices[i] > buyPrice + fee (we can make a profit after paying the fee):
  5. i. Add the profit to the total: profit += prices[i] - buyPrice - fee.
  6. ii. Update buyPrice = prices[i] - fee (adjust the buying price for the next transaction).
  7. Return profit as the maximum profit.

Time Complexity:

O(n)

Where n is the length of the prices array. We iterate through the array once, performing constant-time operations at each step.

Space Complexity:

O(1)

We only use a constant amount of extra space regardless of the input size.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function maxProfit(prices, fee):
    n = length of prices
    if n <= 1:
        return 0
 
    cash = 0  // Maximum profit with no stock
    hold = -prices[0]  // Maximum profit with a stock
 
    for i from 1 to n-1:
        prevCash = cash
        cash = max(cash, hold + prices[i] - fee)  // Sell or keep cash
        hold = max(hold, prevCash - prices[i])  // Buy or keep holding
 
    return cash
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone