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

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}/**2 * @param {number[]} prices3 * @param {number} fee4 * @return {number}5 */6// greedy7var maxProfit = function (prices, fee) {8  const N = prices.length9  let res = 010  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 - fee16      min = prices[i] - fee17      /**18       * we do not make sure i is the final point for sell19       *    so we still have to consider other i20       *    minus fee here to avoid to charge fee double charge21       *    that to understand, but in real case below, it avoids wrong new min assignment22       * for example:23       *    prices: [1, 3, 7, 5, 10, 3]24       *    fee: 325       *26       *    intuitively seen, we buy at prices[0] of 1 and sell at prices[4] of 1027       *    result of 628       *29       *    at prices[2], which is 7, we could sell, 7 - 1 - 3 = 330       *    if that is the final sell, so prices[3], which is 5, will be new min31       *    so the result will be 3 + (10 - 5 - 3) = 5, which is not optimal32       *    so subtract fee here is to add a case for comparision33       *      if prices[3] of 5 is 3 instead, sale is made34       *      otherwise, continue, with a assurance that fee will not be recharge again35       */36    }37  }38  return res39}40
41// dynamic programming (memoized recursion)42var maxProfit = function (prices, fee) {43  const N = prices.length44  const mem = Array.from({ length: N }, _ => Array(2).fill(null))45
46  const recursion = (day, toSell = false) => {47    if (day >= N) {48      return 049    }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] - fee58    } 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}```

## Tags

leetcode

greedy

dynamic programming

recursion

## Next Post

LeetCode: Wiggle Subsequence

Mar 18, 2021

Search Posts