Chapter 7 - General Problems

Question 1

Best time to buy and sell stocks

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5

Answer 1

Define two variables - Min value and Max profit

Min value represents the lowest price in the array at which we can buy a stock.

Loop over the given array and keep updating these values and return the max profit as output in the end.

    min_price = stock_prices[0]
    if len(stock_prices) < 2:
        raise Exception('Nothing to sell')
    max_profit = stock_prices[1] - stock_prices[0]

for idx in range(1, len(stock_prices)): 
    price = stock_prices[idx]
    max_profit = max(max_profit, price-min_price)
    min_price = min(min_price, price)

return max_profit

Complexity: O(n) and O(1) -> time and space