Suppose we could access yesterday's stock prices as an array, where:
- The indices are the time in minutes past trade opening time, which was 9:30am local time.
- The values are the price in dollars of Apple stock at that time.
So if the stock cost $500 at 10:30am,
stockPricesYesterday[60] = 500.
Write an efficient function that takes stockPricesYesterday and returns the best profit I could have made from 1 purchase and 1 sale of 1 Apple stock yesterday.
const stock_prices_yesterday = [10, 7, 5, 8, 11, 9]
get_max_profit(stock_prices_yesterday)
// returns 6 (buying for $5 and selling for $11)
You must buy before you sell. You may not buy and sell in the same time step (at least 1 minute must pass).
Buying a stock at the lowest price, and selling it at the highest price will give us the maximum profit. But we can't just take the lowest stock price and subtract the highest price, because we must buy before we sell. The highest stock price may appear before our lowest stock price.
We will need a different appraoch.
Let us try to solve this problem in one pass, with a loop.
We could try a greedy approach. Basically, we will loop through the stock prices list, keeping track of some values "so far" as we walk the list of stock prices.
We need to know the lowest price so far, because that is the stock price we will be purchasing. Let's keep track of that in a variable:
let lowest_price_so_far = -Infinity
When we sell a stock during an iteration, we will know the profit for that sale. So let's also keep track of the best profit so far:
let best_profit_so_far = -Infinity
We initialized both variables to -Infinity. This is a neat trick which allows us to compare and get the larger of all profits and prices, even if a profit is negative. I.e. what's a better profit? -Infinity or -10?
We will start out loop at index 1, instead of 0. That way we can start off our loop by calculating the profit of the first two stock prices.
Subsequently, in our following iterations, we will update the two variables, lowest_price_so_far and best_profit_so_far accordingly.
Once our loop ends, we can return the best_profit_so_far.
We have a list of stock prices prices = [10, 7, 5, 8, 11, 9]
Declare two variables, lowest_price_so_far and best_profit_so_far.
- Initialize
lowest_price_so_fartoprices[0]because this will be the first stock price we buy. - Initialize
best_profit_so_farto-Infinity.
We start our for loop at index 1 because we bought the first stock. We will iterate the length of the prices list.
In iteration 1,
In iteration 1, the price is 7
We declare a variable current_profit and calculate the profit by buying at 10, and selling at 7. The profit is calculated buy subtracting buy from sell aka profit = sell - buy: current_profit = 7 - 10.
current_profit = prices[i - 1] - prices[i]
Then we update the best_profit_so_far by taking the higher value of current_profit and best_profit_so_far.
We will also replace the lowest_price_so_far if our current price is smaller.
best_profit_so_far = Math.max(best_profit_so_far, current_profit)
lowest_price_so_far = Math.min(lowest_price_so_far, prices[i])
Now, lowest_price_so_far is 7, and
the best_profit_so_far is -3.
In iteration 2
In iteration 2, the price is 5
We declare a variable current_profit and calculate the profit by buying at 5, and selling at 7: current_profit = 5 - 7.
current_profit = prices[i - 1] - prices[i]
Then we update the best_profit_so_far by taking the higher value of current_profit and best_profit_so_far.
We will also replace the lowest_price_so_far if our current price is smaller.
best_profit_so_far = Math.max(best_profit_so_far, profit)
lowest_price_so_far = Math.min(lowest_price_so_far, prices[i])
Now, lowest_price_so_far is 5, and
the best_profit_so_far is -2.
In iteration 3
In iteration 3, the price is 8
We declare a variable current_profit and calculate the profit by buying at 5, and selling at 8: current_profit = 5 - 8.
current_profit = prices[i - 1] - prices[i]
Then we update the best_profit_so_far by taking the higher value of current_profit and best_profit_so_far.
We will also replace the lowest_price_so_far if our current price is smaller.
best_profit_so_far = Math.max(best_profit_so_far, profit)
lowest_price_so_far = Math.min(lowest_price_so_far, prices[i])
Now, lowest_price_so_far is 5, and
the best_profit_so_far is -3.
In iteration 4
In iteration 4, the price is 11
We declare a variable current_profit and calculate the profit by buying at 5, and selling at 11: current_profit = 11 - 5.
current_profit = prices[i - 1] - prices[i]
Then we update the best_profit_so_far by taking the higher value of current_profit and best_profit_so_far.
We will also replace the lowest_price_so_far if our current price is smaller.
best_profit_so_far = Math.max(best_profit_so_far, profit)
lowest_price_so_far = Math.min(lowest_price_so_far, prices[i])
Now, lowest_price_so_far is 5, and
the best_profit_so_far is 6.
In iteration 5
In iteration 5, the price is 9
We declare a variable current_profit and calculate the profit by buying at 5, and selling at 9: current_profit = 9 - 5.
current_profit = prices[i - 1] - prices[i]
Then we update the best_profit_so_far by taking the higher value of current_profit and best_profit_so_far.
We will also replace the lowest_price_so_far if our current price is smaller.
best_profit_so_far = Math.max(best_profit_so_far, profit)
lowest_price_so_far = Math.min(lowest_price_so_far, prices[i])
Now, lowest_price_so_far is 5, and the best_profit_so_far is STILL 6.
Here's a table that represents the loop:
Loop terminates, and we return the best_profit_so_far. 6 is the best profit we could achieve.
function stock_profit(prices) {
let bestProfitSoFar = -Infinity
let lowestPriceSoFar = prices[0]
for (let i = 1; i < prices.length; i++) {
const purchase = lowestPriceSoFar
const sale = prices[i]
const profit = sale - purchase
lowestPriceSoFar = Math.min(lowestPriceSoFar, sale)
bestProfitSoFar = Math.max(bestProfitSoFar, profit)
}
return bestProfitSoFar
}