Problem Explanation:

In this problem, you are given an array of integers representing the stock prices on different days and a fee for each transaction. You ought to perform as many transactions as possible such that the profit is maximized. Multiple transactions can be performed on the same day, however, you are forbidden from owning more than one share of stock at a time, i.e., you need to sell the stock before you can purchase another.

It's important to note that for each transaction, you have to deduct the fee from your profit. The main objective is to figure out the maximum achievable profit.

The problem can be solved by using a dynamic programming strategy where we keep track of two states - the maximum profit we can get for not owning a share on a given day (i.e., we've sold the share), and the maximum profit we can get for owning a share on a given day (i.e., we've bought a share).

Let's consider the following example: prices = [1, 3, 2, 8, 4, 9], fee = 2.

Here, the maximum profit can be achieved as follows:

• Buying at prices[0] = 1
• Selling at prices[3] = 8
• Buying at prices[4] = 4
• Selling at prices[5] = 9

The total profit would then be ((8 - 1) - 2) + ((9 - 4) - 2) which is equal to 8.

Solution Implementations:

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int maxProfit(vector<int>& prices, int fee) {
6    int sell = 0;
7    int hold = INT_MIN;
8
9    for (const int price : prices) {
10      sell = max(sell, hold + price);
11      hold = max(hold, sell - price - fee);
12    }
13
14    return sell;
15  }
16};

Python Solution

1
2python
3class Solution:
4    def maxProfit(self, prices: List[int], fee: int) -> int:
5        sell, hold = 0, -prices[0]
6        for price in prices[1:]:
7            sell, hold = max(sell, hold + price - fee), max(hold, sell - price)
8        return sell

Java Solution

1
2java
3class Solution {
4    public int maxProfit(int[] prices, int fee) {
5        int sell = 0, hold = -prices[0];
6        for(int i = 1; i < prices.length; i++){
7            sell = Math.max(sell, hold + prices[i] - fee);
8            hold = Math.max(hold, sell - prices[i]);
9        }
10        return sell;  
11    }
12}

JavaScript Solution

1
2javascript
3class Solution {
4    maxProfit(prices, fee) {
5        let sell = 0, hold = -prices[0];
6        for(let i = 1; i < prices.length; i++){
7            sell = Math.max(sell, hold + prices[i] - fee);
8            hold = Math.max(hold, sell - prices[i]);
9        }
10        return sell;  
11    }
12}

C# Solution

1
2csharp
3public class Solution {
4    public int MaxProfit(int[] prices, int fee) {
5        int sell = 0, hold = -prices[0];
6        for(int i=1; i<prices.Length; i++){
7            var prevSell = sell;
8            sell = Math.Max(sell, hold + prices[i] - fee);
9            hold = Math.Max(hold, prevSell - prices[i]);
10        }
11        return sell;
12    }
13}

All the solution implementations mentioned above use a similar strategy to solve this problem.

They all follow the iterative approach instead of recursion which makes these solutions efficient. The approach starts by initializing two variables as sell and hold. The sell variable represents the maximum profit we can get by not owning a stock, whilst the hold variable signifies the maximum profit by owning a stock. At the start, we initialize sell with 0, since we have not made any transaction, and hold with negative price of the first day, considering we buy the stock from the money we don't have.

The logic is then applied in a loop from the second day to the last, in which for each price, the sell and hold variables are updated. The sell value is updated by taking the maximum of existing sell and the profit we could generate by getting the price for the day and deducting the fee after selling the stock we're holding. The hold value is updated by taking the maximum of existing hold and the profit achieved by getting the updated sell value and deducting the price for this day (which means buying a stock).

In the end, since the problem asks for the maximum profit when we have no stocks in our portfolio, we return the sell value. This results in the maximum profit calculation after buying and selling stocks and paying the fee each time we sell a stock.

These solutions take O(n) time where n is the number of days (prices length), and O(1) space, making them efficient for large numbers of prices. The solutions are tested and accepted on LeetCode.