Last active
February 1, 2020 17:33
-
-
Save jtrein/f39c15d0efc4a7e1fd0aa32c9887a5bf to your computer and use it in GitHub Desktop.
Greedy Algorithm in JavaScript - Max Profit on Stock Prices (with comments)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Greedy Algorithm (maximum daily profit from stock sale) - "let me see what my options are, first..." | |
| * | |
| * Overview: | |
| * --------- | |
| * By using Greedy Algorithms we can pass over the data once (O(n) time), storing values we find to be optimal, per our criteria, by | |
| * comparing them to current values. We have to go over the entire set to do this, but we only have to do it once - yay! | |
| * | |
| * From Wikipedia: "A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal | |
| * choice at each stage with the hope of finding a global optimum." | |
| * | |
| * NOTE: This is my take on an interview answer to question taken from: https://www.interviewcake.com/question/javascript/stock-price | |
| * | |
| * @param pricesArr {arr} | |
| * @returns int | |
| */ | |
| function getMaxProfit(pricesArr) { | |
| // make sure we have at least 2 prices | |
| if (stockPricesYesterday.length < 2) { | |
| throw new Error('Getting a profit requires at least 2 prices'); | |
| } | |
| // init our first possible "buy price" (minPrice) | |
| var minPrice = pricesArr[0] | |
| // init our first possible maxProfit | |
| // the first 2 values in our array that can derive a profit figure | |
| // subtract our first "sell" price from our first "buy" price | |
| var maxProfit = pricesArr[1] - pricesArr[0] | |
| // init minIndex for comparisons on where we last set our minPrice | |
| var minIndex = 0 | |
| // begin at 1, since we already have our first | |
| for (var i = 1, length = pricesArr.length; i < length; ++i) { | |
| if (pricesArr[i] - minPrice > maxProfit) { | |
| maxProfit = pricesArr[i] - minPrice | |
| } | |
| // set new minPrice: if our current price is lower than our | |
| // set minimum price of the day, then set the new minimum price | |
| // to equal that of the current price | |
| // NOTE: we check to eliminate the last price of day from being set, as the day is over | |
| if (pricesArr[i] < minPrice && i !== length - 1) { | |
| minPrice = pricesArr[i] | |
| minIndex = i | |
| } | |
| } | |
| return maxProfit | |
| } | |
| // boo, bearish market! | |
| var stockPricesYesterday = [18, 17, 13, 11, 5, 1]; | |
| getMaxProfit(stockPricesYesterday) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
For line 19, it should be
pricesArr.length