Problem
This problem was asked by Facebook.
Given an array of numbers representing the stock prices of a company in chronological order, write a function that calculates the maximum profit you could have made from buying and selling that stock once. You must buy before you can sell it.
For example, given [9, 11, 8, 5, 7, 10], you should return 5, since you could buy the stock at 5 dollars and sell it at 10 dollars.
Step 1:Brute Force
The brute force solution here is to iterate over our list of stock prices, and for each price, find the largest profit you can make from selling that stock price (with the formula future - current), and keep track of the largest profit we can find. You should be able to code it up on your own in 5-10 minutes at most.
def buy_and_sell(arr):
max_profit = 0
for i in range(len(arr) - 1):
for j in range(i, len(arr)):
buy_price, sell_price = arr[i], arr[j]
max_profit = max(max_profit, sell_price - buy_price)
return max_profit
This solution takes O(n^2) time and constant space. How do we improve it?
Step 2: Analyzing What We Are Given
The hard part about stock trading is that we never know when it will peak. This is not a problem for this question. We are given all the prices over a time period. Furthermore, we only need to maximize one single trade, not the overall profit.
So what do we do?
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.