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