## Problem

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)

### Naive Solution

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(N^{2}) 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_lowest`

and `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[0] last_highest = prices[0] 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 >>Given an array containing N integers, write a class that contains two functions: and update function that will update a value at a given index, and a sum function that will sum all values between indexes I1 and I2.

Read More >>