[EPI] 5.6 Buy and Sell A Stock Once

Buy and Sell a Stock Once - Elements of Programming Interviews (EPI)

Problem:

Write a program that takes an array denoting daily stock price and returns the max profit made by buying and selling one share of that stock. No need to buy if no profit possible.

Solution:

The naive solution would be to iterate over the list and calculate the difference in current price and all future prices and record highest profit.This will be ~\(O(n^2)\) runtime. A better solution would be to simply keep track of the lowest stock price seen so far as we iterate over the list. Calculate the profit with respect to the lowest stock price seen so far and record the highest possible profit.

def buy_and_sell_stock_once(prices: List[float]) -> float:
    """Function to return the highest possible profit with
    only 1 buy and 1 sell, given a list of stock prices
    over time"""
    profit = 0.0
    min_so_far = float("inf")
    for p1 in prices:
        min_so_far = p1 if p1 < min_so_far else min_so_far  # min(p1, min_so_far) takes longer.
        profit = p1 - min_so_far if p1 - min_so_far > profit else profit  # max(profit, p1 - min_so_far) takes longer.
    return profit

Variant: Write a program that takes an array of integers and finds the length of a longest subarray all of whose entries are equal.

def longest(array):
    length, tmp = 0, 1
    for i, num in enumerate(array):
        if num == array[i-1]:
            tmp += 1
        else:
            length = tmp if tmp > length else length
            tmp = 1
    length = tmp if tmp > length else length  # If longest subarray is at end of array
    return length