Best Time to Buy and Sell Stock with Transaction Fee — LeetCode 714 Python Solution
MediumGreedyArrayDynamic Programming
- Problem
- #714
- Pattern
- Greedy
- Reading time
- 3 min
- Source
- leetcode.com
The 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.
Example
- Input
- prices = [1,3,2,8,4,9], fee = 2
- Output
- 8
- Explanation
- The maximum profit can be achieved by:
Python solution
Python
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i >= len(prices):
return 0
ans = dfs(i + 1, j)
if j:
ans = max(ans, prices[i] + dfs(i + 1, 0) - fee)
else:
ans = max(ans, -prices[i] + dfs(i + 1, 1))
return ans
return dfs(0, 0)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
On a study list
This problem is on LeetCode 75.
Frequently asked questions
- How hard is LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee?
- LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee is rated Medium on LeetCode.
- What is the time complexity of LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee cover?
- LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee is tagged Greedy, Array and Dynamic Programming on LeetCode.