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

1/**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}4041// dynamic programming (memoized recursion)42var maxProfit = function (prices, fee) {43 const N = prices.length44 const mem = Array.from({ length: N }, _ => Array(2).fill(null))4546 const recursion = (day, toSell = false) => {47 if (day >= N) {48 return 049 }5051 if (mem[day][toSell] != null) {52 return mem[day][toSell]53 }5455 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)6263 return (mem[day][toSell] = Math.max(buy, sell, noop))64 }6566 return recursion(0)67}

## Comments

Loading comments...

## Tags

leetcode

greedy

dynamic programming

recursion

## Apply and earn a $2,500 bonus once you're hired on your first job!

Clients from the Fortune 500 to Silicon Valley startups

Choose your own rate, get paid on time

From hourly, part-time, to full-time positions

Flexible remote working environment

A lot of open JavaScript jobs!!

**Fact corner:** Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.

**Still hesitate?** Read HoningJS author's guide on dealing with Toptal interview process.

## Next Post

LeetCode: Wiggle Subsequence

Mar 18, 2021

## Previous Post

LeetCode: Encode And Decode Tinyurl

Mar 15, 2021