Solution: Best Time to Buy and Sell Stock with Transaction Fee

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #714 (Medium): Best Time to Buy and Sell Stock with Transaction Fee

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

---

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 * 10^4
• 0 < prices[i], fee < 5 * 10^4

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

This proplem is an introduction to state machine logic. In order to solve it, we can consider the two possible distinct states of being: having no stock and being ready to buy (buying) and owning stock and being ready to sell (selling).

We just need to iterate through the prices (P) and keep track of the best possible value for these two states of being for each day. The difficulty is that the tracks of the two states cross over regulary.

For example, if we consider the state of being ready to buy stock after this iteration (buying), it can be reached from being ready to buy today and doing nothing, OR it can be reached by being ready to sell today and selling (with the additional fee [F]). We just need to pick whichever one yields the best value.

The same is true of the selling state. The new selling state is the better result between the previous selling state with no action and the previous buying state with a stock purchase today.

We should manually set our initial values for buying and selling to account for the first day and iterate from there.

Since the fee is only administered once per buy/sell pair, we can technically account for it on either side, as we're always going to want to return the buying state, having no outstanding stock left to sell.

Question: Should we be worried about updating buying before using it in the second equation?
Mathematically, it's only ever a good day to buy or sell; it cannot be both.

Consider the possible situations: In the first equation, if the old buying is greater than selling + P[i] - F, then the new buying will be the same as the old buying, so there will be no change for the second equation.

But what if buying changes? Let's take an example:

  if:  buy = 10, P[i] = 4, F = 0
then:  newBuy = max(10, sell + 4 - 0)
       newSell = max(sell, newBuy - 4)

  if:  sell <= 6                          // For values of sell less than 7
then:  newBuy = max(10, <=10)             // the old buy will still be largest
       newBuy = buy                       // so there's no problem

  if:  sell > 6                           // If sell is greater than 6
then:  newBuy = max(10, >6 + 4)           // then buy will change
       newBuy = sell + 4                  // so we might have a problem

  if:  newBuy = sell + 4                  // But here we see that sell cannot
then:  newSell = max(sell, sell + 4 - 4)  // possibly change when buy does

Any positive value for F in the above example would only lower the value of newBuy, which would only make it so that newBuy - P[i] couldn't even tie sell but would always be lower.

---

Implementation:

The code for all four languages is almost identical.

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var maxProfit = function(P, F) {
    let len = P.length, buying = 0, selling = -P[0]
    for (let i = 1; i < len; i++) {
        buying = Math.max(buying, selling + P[i] - F)
        selling = Math.max(selling, buying - P[i])
    }
    return buying
};

---

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def maxProfit(self, P: List[int], F: int) -> int:
        buying, selling = 0, -P[0]
        for i in range(1, len(P)):
            buying = max(buying, selling + P[i] - F)
            selling = max(selling, buying - P[i])
        return buying

---

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int maxProfit(int[] P, int F) {
        int len = P.length, buying = 0, selling = -P[0];
        for (int i = 1; i < len; i++) {
            buying = Math.max(buying, selling + P[i] - F);
            selling = Math.max(selling, buying - P[i]);
        }
        return buying;
    }
}

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int maxProfit(vector<int>& P, int F) {
        int len = P.size(), buying = 0, selling = -P[0];
        for (int i = 1; i < len; i++) {
            buying = max(buying, selling + P[i] - F);
            selling = max(selling, buying - P[i]);
        }
        return buying;
    }
};