LeetCode: Best Time To Buy And Sell Stock With Transaction Fee Solution

1/**
2 * @param {number[]} prices
3 * @param {number} fee
4 * @return {number}
5 */
6// greedy
7var maxProfit = function (prices, fee) {
8  const N = prices.length
9  let res = 0
10  let min = prices[0]
11  for (let i = 1; i < N; i++) {
12    if (prices[i] < min) {
13      min = prices[i]
14    } else if (prices[i] - min - fee > 0) {
15      res += prices[i] - min - fee
16      min = prices[i] - fee
17      /**
18       * we do not make sure i is the final point for sell
19       *    so we still have to consider other i
20       *    minus fee here to avoid to charge fee double charge
21       *    that to understand, but in real case below, it avoids wrong new min assignment
22       * for example:
23       *    prices: [1, 3, 7, 5, 10, 3]
24       *    fee: 3
25       *
26       *    intuitively seen, we buy at prices[0] of 1 and sell at prices[4] of 10
27       *    result of 6
28       *
29       *    at prices[2], which is 7, we could sell, 7 - 1 - 3 = 3
30       *    if that is the final sell, so prices[3], which is 5, will be new min
31       *    so the result will be 3 + (10 - 5 - 3) = 5, which is not optimal
32       *    so subtract fee here is to add a case for comparision
33       *      if prices[3] of 5 is 3 instead, sale is made
34       *      otherwise, continue, with a assurance that fee will not be recharge again
35       */
36    }
37  }
38  return res
39}
40
41// dynamic programming (memoized recursion)
42var maxProfit = function (prices, fee) {
43  const N = prices.length
44  const mem = Array.from({ length: N }, _ => Array(2).fill(null))
45
46  const recursion = (day, toSell = false) => {
47    if (day >= N) {
48      return 0
49    }
50
51    if (mem[day][toSell] != null) {
52      return mem[day][toSell]
53    }
54
55    let [sell, buy, noop] = [0, 0, 0]
56    if (toSell) {
57      sell = recursion(day + 1, false) + prices[day] - fee
58    } else {
59      buy = recursion(day + 1, true) - prices[day]
60    }
61    noop = recursion(day + 1, toSell)
62
63    return (mem[day][toSell] = Math.max(buy, sell, noop))
64  }
65
66  return recursion(0)
67}