Sponsored
Sponsored
This approach uses dynamic programming to track three states on each day: holding, not holding with cooldown, and not holding without cooldown. The idea is to decide the best action for any day based on the previous day's states. At each step, calculate the maximum profit for holding a stock, selling it, or being idle.
Time Complexity: O(n), where n is the number of days. Each day's prices are visited once.
Space Complexity: O(1), since only a fixed amount of extra space is used.
1function maxProfit(prices) {
2 if (prices.length === 0) return 0;
3 let hold = -prices[0], sell = 0, cooldown = 0;
4 for (let i = 1; i < prices.length; i++) {
5 let prev_sell = sell;
6 sell = hold + prices[i];
7 hold = Math.max(hold, cooldown - prices[i]);
8 cooldown = Math.max(cooldown, prev_sell);
9 }
10 return Math.max(sell, cooldown);
11}
12
13console.log("Max Profit:", maxProfit([1, 2, 3, 0, 2]));The JavaScript function maxProfit operates by iterating through the price list and updates state variables hold, sell, and cooldown to manage possible transitions and maximize profits.
This approach involves a recursive solution that tracks the profit by exploring all possible transactions. To optimize the solution, memoization is used to store and reuse results of repeated states to avoid redundant calculations.
Time Complexity: O(n), where n is the number of days. Thanks to memoization, each state is computed once.
Space Complexity: O(n), for the memoization table.
using System.Collections.Generic;
public class Solution {
private Dictionary<Tuple<int, int>, int> memo = new Dictionary<Tuple<int, int>, int>();
public int Solve(int[] prices, int i, int canBuy) {
if (i >= prices.Length) return 0;
var key = Tuple.Create(i, canBuy);
if (memo.ContainsKey(key)) return memo[key];
int cooldown = Solve(prices, i + 1, canBuy);
if (canBuy == 1) {
int buy = Solve(prices, i + 1, 0) - prices[i];
memo[key] = Math.Max(buy, cooldown);
} else {
int sell = Solve(prices, i + 2, 1) + prices[i];
memo[key] = Math.Max(sell, cooldown);
}
return memo[key];
}
public int MaxProfit(int[] prices) {
return Solve(prices, 0, 1);
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] prices = {1, 2, 3, 0, 2};
Console.WriteLine("Max Profit: " + sol.MaxProfit(prices));
}
}The C# version leverages a dictionary to store results of function calls for quick lookup, ensuring each state (day and canBuy status) is computed once. This recursive approach ensures maximum profit paths are explored without redundancy.