LeetCode //C - 714. Best Time to Buy and Sell Stock with Transaction Fee

714. Best Time to Buy and Sell Stock with Transaction Fee

You are given an array prices where prices[i] is the price of a given stock on the $i^{th}$ day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note:

• You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
• The transaction fee is only charged once for each stock purchase and sale.
   

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\ast 10^4$
• $1<=prices[i]<5\ast 10^4$
• $0<=fee<5\ast 10^4$

From: LeetCode
Link: 714. Best Time to Buy and Sell Stock with Transaction Fee

Solution:

Ideas：

This function iterates over each price in prices and at each step, calculates the maximum profit for holding and not holding a stock, considering the transaction fee. The maximum profit when not holding a stock is either the same as the previous day if no action is taken, or it is the profit from selling the stock held previously plus the current price minus the transaction fee. The maximum profit for holding a stock is either the same as the previous day if no action is taken, or it’s the profit from buying a stock that day, which is the previous day’s profit without holding a stock minus the current price and the transaction fee.

At the end of the iteration, notHold will contain the maximum profit achievable without holding any stock, which is the result we want to return.

Caode:

int maxProfit(int* prices, int pricesSize, int fee) {
   
    // Initialize variables to store the maximum profit when holding and not holding a stock.
    // notHold is initialized to 0 since we start with no stock.
    // hold is initialized to -prices[0] - fee to represent buying the stock on the first day.
    int notHold = 0, hold = -prices[0] - fee;
    
    for (int i = 1; i < pricesSize; i++) {
   
        // Update notHold to be the maximum of itself and hold + prices[i].
        // This represents not holding any stock on day i.
        int prevNotHold = notHold;
        notHold = hold + prices[i] > notHold ? hold + prices[i] : notHold;
        
        // Update hold to be the maximum of itself and prevNotHold - prices[i] - fee.
        // This represents holding a stock on day i.
        hold = prevNotHold - prices[i] - fee > hold ? prevNotHold - prices[i] - fee : hold;
    }
    
    // The maximum profit is when we do not hold any stock at the end.
    return notHold;
}