Write a function that takes an array of ticker prices for a given stock, and returns the maximum profit possible in that time frame. In order to realize the profit, a sale of the stock must happen after a purchase.
As an example:
[100, 99, 98, 98, 105, 106, 100, 90, 91, 98, 113, 112] # returns 23 (buy at 90, sell at 113)
The simple solution is to have two for loops that iterate through the array, and check every valid combination for the greatest value. This is an O(N2) solution.
def maximum_profit(prices): max_profit = 0 for spi in range(0, len(prices)): for epi in range(spi, len(prices)): max_profit = max(max_profit, prices[epi] - prices[spi]) return max_profit
A Linear Solution
As with a lot of these questions, there is a better way to solve this problem, and specifically, there is a way to solve it in linear time. The trick is to keep track of two pointers, one for the last lowest price we have seen, and another for the last highest price. As we iterate through our array of prices, we compare our current price to our
last_highest price, and take the higher of the two. We then compare our current price to our
last_lowest price, and if the current price is lower, we check if
last_highest - last_lowest is a greater value than our current
max_profit (and if it is, we set that as our new
max_profit), we then set our
last_highest to the current price. At the end of iterating throught the array,
max_profit will contain the greatest profit in the series.
def maximum_profit(prices): if len(prices) == 0: return 0 last_lowest = prices last_highest = prices max_profit = 0 for price in prices[1:]: if price > last_highest: last_highest = price max_profit = max(max_profit, last_highest - last_lowest) elif price < last_lowest: last_highest = price last_lowest = price return max_profit
You may also want to read:
You are given an array that is comprised of positive integers. Initially, these numbers are ascending, but at some point they start descending. There are no duplicate integers in the array. Find the index of the maximum value.Read More >>
Write a function that takes a sorted list, and returns a number that is "over represented". A number is considered over represented if it occurs at least ceil(N/4) times in the list, where N is the length of the list.Read More >>