https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee

Let us define diff[i] = B[i+1] - B[i]. Then we need to find maximum gain for several continuous subarrays, where we pay fee for each subarray. Let us consider it on example: [1, 3, 5, 4, 8, 7, 4], then differences will be [2, 2, -1, 4, -1, -3]. For example we can take two subarrays [2, 2] and [4], it means we make two trancastions and we need to pay 2 fees. In original array it means we buy at price 1, then sell at price 5. Then buy at price 4 and sell at price 8.

Use dynamic programming, where dp[i] is maximum gain at i-th moment of time if we use diff[i] and sp[i] be maximum among dp[0], ..., dp[i], that is running maximum, that is sp[i] is the gain we can get, using first i times. Then we can have 2 options:

  1. We continue last subarray, so we get diff[i] + dp[i-1].
  2. We start new subarray, so we get diff[i] + sp[i-2] - fee: here we take sp[i-2], because we need to skip one element, so subarrays are separated.

Let us look at our example with differences [2, 2, -1, 4, -1, -3]:

1.dp[0] is the maximum gain we can get using ony first difference, we can have 2 and we need to pay fee, so we have 1.

2.dp[1] is maxumum gain we can get using [2, 2]. We can continue previous transaction, so we will gain 3. Or we can try to start new transaction. However it is not possible, because we need to have a gap here.

3.dp[2] is maximum gain we can get using [2, 2, -1]. Note, that by definition of dp[i] we need to use last element here, so again we have two choices: if we continue first transaction, we have 3-1 = 2 gain. Or we start new transaction, and then we need to make gap and previous transaction will be for element i-2 or smaller. Exaclty for this we use sp: running maximum of dp. In our case sp[0] = 1, so total gain if we start new transaction is sp[0] - fee + -1 = -1.

4.dp[3] is maximum gain we can get using [2, 2, -1, 4]. Again, we can have two choices: continue last transaction, in this case we have dp[2] + 4 = 6. If we start new transaction, we have sp[1] - fee + 4 = 6 as well. So in this case does not matter, what option we choose and it makes sence: fee is equal to decrease of price.

5.dp[4] is maximum gain we can get using [2, 2, -1, 4, -1]. Again, we have choice between dp[3] + -1 = 5 and sp[2] - fee + -1 = 4.

6.dp[5] is maximum gain we can get using [2, 2, -1, 4, -1, -3]. We have either dp[4] + -3 = 2 or sp[3] - fee + -3 = 2.

Finally, we have arrays like this:

dp = [1, 3, 2, 6, 5, 2, -inf] sp = [1, 3, 3, 6, 6, 6, 0]

Complexity: time and space complexity is O(n), where space complexity can be reduced to O(1), because we use only 2 elements to the back.

class Solution:
    def maxProfit(self, B, fee):
        if len(B) == 1: return 0
        n = len(B)
        
        dp, sp = [-float(inf)]*n, [0]*n

        for i in range(n-1):
            dp[i] = B[i+1] - B[i] + max(dp[i-1], sp[i-2] - fee)
            sp[i] = max(sp[i-1], dp[i])
             
        return sp[-2]

Other buy and sell stock problems with my explanations:

121: Best Time to Buy and Sell Stock 123. Best Time to Buy and Sell Stock III 188. Best Time to Buy and Sell Stock IV

If you like the solution, you can upvote it on leetcode discussion section: Problem 0714