Sponsored
Sponsored
In 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.
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.
1var maxProfit = function(prices, fee) {
2 let cash = 0, hold = -prices[0];
3 for (let i =
The JavaScript solution uses two state variables, cash and hold, initialized to represent starting conditions. For each price in the array, the script updates these values with Math.max, ensuring that the most advantageous choice for either selling or buying is taken each day.
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.
Time Complexity: O(N), since it processes each price once.
Space Complexity: O(1), using a constant set of additional variables.
Java's implementation uses a for loop over the price array, keeping track of the current minimum price at which buying/selling leads to profit. Transaction fees are integrated to update potential profits.