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.
public class Solution {
public int MaxProfit(int[] prices, int fee) {
int maxProfit = 0, minPrice = prices[0];
for (int i = 1; i < prices.Length; ++i) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] > minPrice + fee) {
maxProfit += prices[i] - minPrice - fee;
minPrice = prices[i] - fee;
}
}
return maxProfit;
}
public static void Main(string[] args) {
var sol = new Solution();
int[] prices = {1, 3, 2, 8, 4, 9};
int fee = 2;
Console.WriteLine("Maximum profit: " + sol.MaxProfit(prices, fee));
}
}The C# solution adopts a logical pattern consistent with other greedy implementations, determining to sell stock when it yields net gain surpassing the fee, and adjusting trackers thereafter.