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
/**
 * Find the maximum profit with transaction fees.
 * Dynamic Programming approach.
 *
 * @param {number[]} prices - Array of stock prices
 * @param {number} fee - Transaction fee
 * @return {number} - Maximum profit
 */
function maxProfit(prices, fee) {
  if (prices.length <= 1) {
    return 0;
  }
 
  let cash = 0;  // Maximum profit with no stock
  let hold = -prices[0];  // Maximum profit with a stock
 
  for (let i = 1; i < prices.length; i++) {
    // We need to use temporary variables to avoid using the updated cash value when calculating hold
    const prevCash = cash;
 
    // Sell or keep cash
    cash = Math.max(cash, hold + prices[i] - fee);
 
    // Buy or keep holding
    hold = Math.max(hold, prevCash - prices[i]);
  }
 
  return cash;
}
 
/**
 * Find the maximum profit with transaction fees.
 * State Machine approach.
 *
 * @param {number[]} prices - Array of stock prices
 * @param {number} fee - Transaction fee
 * @return {number} - Maximum profit
 */
function maxProfitStateMachine(prices, fee) {
  if (prices.length <= 1) {
    return 0;
  }
 
  let s0 = 0;  // Maximum profit with no stock
  let s1 = -prices[0];  // Maximum profit with a stock
 
  for (let i = 1; i < prices.length; i++) {
    // We need to use temporary variables to avoid using the updated s0 value when calculating s1
    const prevS0 = s0;
 
    // State 0: No stock, either stay or sell
    s0 = Math.max(s0, s1 + prices[i] - fee);
 
    // State 1: Have stock, either stay or buy
    s1 = Math.max(s1, prevS0 - prices[i]);
  }
 
  return s0;
}
 
/**
 * Find the maximum profit with transaction fees.
 * Greedy approach.
 *
 * @param {number[]} prices - Array of stock prices
 * @param {number} fee - Transaction fee
 * @return {number} - Maximum profit
 */
function maxProfitGreedy(prices, fee) {
  if (prices.length <= 1) {
    return 0;
  }
 
  let profit = 0;
  let buyPrice = prices[0];
 
  for (let i = 1; i < prices.length; i++) {
    if (prices[i] < buyPrice) {
      // Found a lower buying price
      buyPrice = prices[i];
    } else if (prices[i] > buyPrice + fee) {
      // We can make a profit after paying the fee
      profit += prices[i] - buyPrice - fee;
 
      // Adjust buying price for the next transaction
      // This is a key insight: we can effectively "hold" the stock by setting the buy price to the current price minus the fee
      buyPrice = prices[i] - fee;
    }
  }
 
  return profit;
}
 
// Test cases
console.log(maxProfit([1, 3, 2, 8, 4, 9], 2));  // 8
console.log(maxProfit([1, 3, 7, 5, 10, 3], 3));  // 6
 
console.log(maxProfitStateMachine([1, 3, 2, 8, 4, 9], 2));  // 8
console.log(maxProfitStateMachine([1, 3, 7, 5, 10, 3], 3));  // 6
 
console.log(maxProfitGreedy([1, 3, 2, 8, 4, 9], 2));  // 8
console.log(maxProfitGreedy([1, 3, 7, 5, 10, 3], 3));  // 6