1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/**
 * Find the maximum profit with cooldown.
 * State Machine approach.
 *
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfit(prices) {
  if (prices.length <= 1) {
    return 0;
  }
 
  let hold = -prices[0];  // Maximum profit with a stock
  let sold = 0;  // Maximum profit after selling
  let rest = 0;  // Maximum profit at rest
 
  for (let i = 1; i < prices.length; i++) {
    // We need to use temporary variables to avoid using updated values in the same iteration
    const prevHold = hold;
 
    // Continue holding or buy
    hold = Math.max(hold, rest - prices[i]);
 
    // Sell the stock
    sold = prevHold + prices[i];
 
    // Continue resting or come from sold
    rest = Math.max(rest, sold);
  }
 
  return Math.max(sold, rest);
}
 
/**
 * Find the maximum profit with cooldown.
 * Dynamic Programming approach.
 *
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfitDP(prices) {
  if (prices.length <= 1) {
    return 0;
  }
 
  const n = prices.length;
  const buy = new Array(n).fill(0);
  const sell = new Array(n).fill(0);
  const cooldown = new Array(n).fill(0);
 
  buy[0] = -prices[0];
 
  for (let i = 1; i < n; i++) {
    // Buy: continue from previous buy state or buy after cooldown
    buy[i] = Math.max(buy[i - 1], cooldown[i - 1] - prices[i]);
 
    // Sell: continue from previous sell state or sell the stock we bought
    sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
 
    // Cooldown: continue from previous cooldown state or enter cooldown after selling
    cooldown[i] = Math.max(cooldown[i - 1], sell[i - 1]);
  }
 
  return Math.max(sell[n - 1], cooldown[n - 1]);
}
 
/**
 * Find the maximum profit with cooldown.
 * Optimized Dynamic Programming approach.
 *
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfitOptimized(prices) {
  if (prices.length <= 1) {
    return 0;
  }
 
  let buy = -prices[0];
  let sell = 0;
  let cooldown = 0;
 
  for (let i = 1; i < prices.length; i++) {
    // We need to use temporary variables to avoid using updated values in the same iteration
    const prevBuy = buy;
    const prevSell = sell;
 
    // Buy: continue from previous buy state or buy after cooldown
    buy = Math.max(buy, cooldown - prices[i]);
 
    // Sell: continue from previous sell state or sell the stock we bought
    sell = Math.max(sell, prevBuy + prices[i]);
 
    // Cooldown: continue from previous cooldown state or enter cooldown after selling
    cooldown = Math.max(cooldown, prevSell);
  }
 
  return Math.max(sell, cooldown);
}
 
// Test cases
console.log(maxProfit([1, 2, 3, 0, 2]));  // 3
console.log(maxProfit([1]));  // 0
 
console.log(maxProfitDP([1, 2, 3, 0, 2]));  // 3
console.log(maxProfitDP([1]));  // 0
 
console.log(maxProfitOptimized([1, 2, 3, 0, 2]));  // 3
console.log(maxProfitOptimized([1]));  // 0