Solution: Best Time to Buy and Sell Stock with Transaction Fee
Tags: algorithms, javascript, java, python
Published: 2021-03-16 08:53:10

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/1112088).*

---

#### [Leetcode Problem #714 (*Medium*): Best Time to Buy and Sell Stock with Transaction Fee](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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).

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|prices = [1,3,2,8,4,9], fee = 2
Output:|8
Explanation:|The maximum profit can be achieved by:<br>- Buying at prices[0] = 1<br>- Selling at prices[3] = 8<br>- Buying at prices[4] = 4<br>- Selling at prices[5] = 9<br>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:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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.

![State Machine Visual](https://i.imgur.com/9hpSjmS.png)

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:
```js
  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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
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;
    }
};
```