Vultr DocsLatest Content

Best Time to Buy and Sell Stock with Transaction Fee

Updated on 14 May, 2025
Best Time to Buy and Sell Stock with Transaction Fee header image

Problem Statement

In the given problem, an array prices represents the price of a specific stock on consecutive days, indexed by the day (starting from zero). Additionally, a transaction fee, denoted as fee, is associated with each buy and sell operation. The goal is to determine the maximum profit possible from buying and selling the stocks under these conditions:

  • You can make as many transactions as needed, where each transaction consists of buying and then later selling the stock.
  • You cannot hold more than one stock at a time, meaning you need to sell the current stock before you can buy another.
  • The transaction fee is applied each time a stock is bought and sold. This fee should be accounted for in the total profit calculation.

To clarify, you should aim to maximize the profit taking into consideration the cost incurred from the transaction fees for each buy-sell pair.

Examples

Example 1

Input:

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

Output:

8

Explanation:

The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Example 2

Input:

prices = [1,3,7,5,10,3], fee = 3

Output:

6

Constraints

  • 1 <= prices.length <= 5 * 104
  • 1 <= prices[i] < 5 * 104
  • 0 <= fee < 5 * 104

Approach and Intuition

To tackle this problem, the key is to determine the optimal times to buy and sell to maximize the net profit after accounting for transaction fees. A straightforward approach involves assessing profit scenarios for each potential transaction day, considering the effect of fees on sale day profits.

  1. Initialization: Start with two variables, hold and cash. hold represents the maximum profit with a stock currently held (after buying), initialized to -prices[0] since we spend that amount buying the stock. cash represents the maximum profit with no stock held currently, initialized to zero.

  2. Iterate through each price: For each day's price after the first:

    • Update hold as the greater value between the existing hold, or cash reduced by the current price (representing buying the stock today).
    • Update cash as the greater value between the existing cash, or hold increased by the current price minus the transaction fee (representing selling the stock today).

    This dynamic approach ensures you evaluate whether holding or selling yields a higher profit at each step while considering the transaction fee impacts.

  3. Profit Calculation: By the end of the price array, cash will contain the maximum profit possible without holding any stock, which essentially is the solution to the problem. The profit on days where transactions occur takes into consideration the subtraction of buy costs and addition of sell revenue, adjusted for fees.

By following this strategy, the algorithm efficiently calculates the maximum profit achievable under the provided constraints, ensuring that transaction sequencing and fee adjustments are properly managed.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int totalDays = prices.size();
        int cash = 0, hold = -prices[0];
        
        for (int day = 1; day < totalDays; day++) {
            int prevHold = hold;
            hold = max(hold, cash - prices[day]);
            cash = max(cash, prevHold + prices[day] - fee);
        }
        
        return cash;
    }
};

The problem "Best Time to Buy and Sell Stock with Transaction Fee" involves determining the maximum profit that can be made from trading stocks given a transaction fee. The solution provided uses C++ and employs a dynamic programming approach to solve the problem efficiently.

The function maxProfit takes two parameters: a vector prices that represents the stock prices over a range of days, and an integer fee that represents the transaction cost for buying or selling the stock. It keeps track of two variables, cash and hold.

  • cash represents the maximum profit achieved so far without currently holding a stock.
  • hold represents the maximum profit achieved so far while holding a stock.

The algorithm initializes cash to 0 (indicating no stock is bought yet) and hold to the negative value of the first stock price (indicating buying the stock on the first day).

For each subsequent day (day), it updates the hold and cash values:

  • hold is updated to be the maximum of itself (not selling the stock today) and cash - prices[day] (buying the stock today).
  • cash is updated to be the maximum of itself (not buying the stock today) and hold + prices[day] - fee (selling the stock today).

At the end of the loop, cash will represent the maximum profit that can be achieved under the given conditions. The function then returns this value.

This algorithm effectively finds the optimal time to buy and sell stocks to maximize profit while accounting for the transaction fee, with a time complexity of O(n), where n is the total number of days.

java 
class Solution {
    public int calculateMaxProfit(int[] stockPrices, int commission) {
        int totalDays = stockPrices.length;
        int profit = 0, holdStock = -stockPrices[0];
        
        for (int currentDay = 1; currentDay < totalDays; currentDay++) {
            int temp = holdStock;
            holdStock = Math.max(holdStock, profit - stockPrices[currentDay]);
            profit = Math.max(profit, temp + stockPrices[currentDay] - commission);
        }
        
        return profit;
    }
}

The given Java program solves the problem of finding the maximum profit that can be made by buying and selling stocks given a transaction fee (commission) for each transaction. The solution employs a dynamic programming approach.

  • The program starts by initializing totalDays to the length of the stockPrices array and two integers profit and holdStock. The profit is initialized to 0, representing no profit initially, and holdStock is initialized to the negative value of the first stock price, representing the purchase of the stock on day 0.

  • Then, the program loops through each day starting from day 1 to calculate the maximum profit. During each iteration:

    • A temporary variable temp is used to temporarily store the value of holdStock.
    • holdStock is updated to the maximum value between its current value and the difference between profit and the current day's stock price. This operation determines whether to continue holding the previously bought stock or to buy a new stock on the current day.
    • profit is updated to the maximum value between its current value and the sum of temp plus the current day's stock price minus the commission. This step calculates the maximum profit achievable either by doing nothing or by selling the stock bought on a previous day considering the transaction fee.

  • After the loop has processed all days, the function returns the value of profit, which represents the maximum achievable profit with the given transaction fee over the provided period.

This method efficiently handles the stock trading scenario by dynamically adjusting buy and sell decisions based on profit maximization while accounting for transaction costs.

python 
class Solution:
    def calculateMaxProfit(self, stock_prices: List[int], transaction_fee: int) -> int:
        days_count = len(stock_prices)
        holding, cash = -stock_prices[0], 0
        
        for day in range(1, days_count):
            prev_hold = holding
            holding = max(holding, cash - stock_prices[day])
            cash = max(cash, prev_hold + stock_prices[day] - transaction_fee)
        
        return cash

The provided Python code aims to solve the problem of determining the maximum profit from trading stocks where each transaction incurs a fixed fee. The function calculateMaxProfit inside the Solution class requires two inputs: stock_prices, a list of integers representing the price of a stock on various days, and transaction_fee, an integer denoting the cost of making a single stock transaction.

Follow these steps to comprehend the approach taken in the code:

  1. Initialize days_count with the number of elements in the stock_prices list.
  2. Establish two variables: holding, to track the maximum profit when holding a stock, initiated with the negative value of the stock price on the first day (assuming an immediate buy), and cash, to track maximum profit when not holding any stocks, initialized to zero.
  3. For each subsequent day, starting from day one:
    • Record the previous holding value.
    • Update the holding to be the maximum between the current holding and cash minus the stock price on the current day. This step accounts for whether it's more profitable to keep holding the previous stock or to buy a new stock after selling any held stock.
    • Update the cash to be the maximum between itself and the result of selling the stock previously held on the current day minus the transaction fee.
  4. After iterating through the days, return the cash value which represents the maximum profit achieved without holding any stocks.

The function effectively uses dynamic programming, where the state of holding and cash at each day depends on their states from the previous day. This approach captures the essence of choosing when to buy and sell stocks to maximize profit while considering the transaction fee at each trade.

Comments

No comments yet.