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:
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 * 1041 <= prices[i] < 5 * 1040 <= fee < 5 * 104In this approach, we use Dynamic Programming to manage two states: whether you're holding a stock or not on each day. The goal is to maximize the profit by deciding to buy, sell, or hold at each step while accounting for the transaction fee.
States: We define two states: hold[i] which represents the maximum profit you can have on day i when holding a stock, and cash[i] which represents the maximum profit on day i when not holding a stock.
State Transitions: On each day, you can either buy a stock (thus moving from cash[i-1] to hold[i]) or sell a stock (thus moving from hold[i-1] to cash[i]). Decisions should include transaction fee accordingly.
The C solution uses two variables, cash and hold, to keep track of the two states we have defined. Initially, cash is set to 0 (since you start with no money from stock), and hold is set to -prices[0] (representing buying a stock on the first day).
For each day, update cash with the maximum of not selling today or selling the stock today with added profit minus fee. Similarly, hold is updated with the maximum of not buying today or buying today by using available cash.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N), where N is the number of days, since we go through the prices once.
Space Complexity: O(1), as we use a fixed amount of extra space regardless of input size.
The greedy approach is an alternative solution that strives to maximize the profit by considering local optimal decisions. Unlike the dynamic approach that tracks two states, this method attempts to buy on dips and sell at peaks whenever possible while covering the transaction fee.
Keep track of the lowest price at which a stock might have been bought, and compare future prices to decide if selling should occur, adjusting the buy price to be less the transaction fee.
This C solution attempts to execute transactions only when it's profitable. It tracks the current minimum price known, and if selling would provide profit after fees, it moves to secure it by updating maxProfit. The minPrice is adjusted post-sale to ensure compliance with transaction costs.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N), since it processes each price once.
Space Complexity: O(1), using a constant set of additional variables.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(N), where N is the number of days, since we go through the prices once. Space Complexity: O(1), as we use a fixed amount of extra space regardless of input size. |
| Greedy Approach | Time Complexity: O(N), since it processes each price once. Space Complexity: O(1), using a constant set of additional variables. |
Sliding Window: Best Time to Buy and Sell Stock - Leetcode 121 - Python • NeetCode • 848,237 views views
Watch 9 more video solutions →Practice Best Time to Buy and Sell Stock with Transaction Fee with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor