[Amazon Question] Best Time to Buy and Sell Stock with Transaction Fee

Problem: You are given an array prices where prices[i] is the price of a given stock on the ith 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 that you can't engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example:

Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[4] = 10
The total profit is (10 - 1 - 3) = 6.

Approach: Like any other Buy and sell stock problem before, we are going to use DP here too. We are going to maintain two variables:

1. maxProfitByHoldingStock: The maximum profit we can have if we hold a stock.
2. maxProfitWithNoStock: The maximum profit we can have if we don't have any stock.

At 0th day, the values of these variables will be:

• maxProfitByHoldingStock = -prices[0] // Buy a stock
• maxProfitWithNoStock = 0 // Can't sell if didn't buy anything.

Now at any ith day, we can either sell a stock or buy a stock:

• Sell a stock: maxProfitWithNoStock  = MAX(maxProfitWithNoStock, maxProfitByHoldingStock + prices[i] - fee)
• Buy a stock: maxProfitByHoldingStock = MAX(maxProfitByHoldingStock, maxProfitWithNoStock - prices[i])

In the end, it is obvious that maxProfitWithNoStock  will be our answer.

Implementation in C#:

    public int MaxProfit(int[] prices, int fee)

    {

        int length = prices?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        int maxProfitWithNoStocks = 0;

        int maxProfitWithStocks = -prices[0];

        for (int i = 1; i < length; ++i)

        {

            maxProfitWithNoStocks = Math.Max(maxProfitWithNoStocks,

                                             maxProfitWithStocks + prices[i] - fee);

            maxProfitWithStocks = Math.Max(maxProfitWithStocks,

                                           maxProfitWithNoStocks - prices[i]);

        }

        return maxProfitWithNoStocks;

    }

Complexity: O(n)