> Interview Breeze

Maximum profit by selling a stock

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(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_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:

Point of Descent

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 >>
Over Represented Number

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 >>
Array Summing

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 >>

Python Console