Best Time to Buy and Sell Stock

+10

You get a list prices, where prices[i] is the price of one stock on day i. You may buy one share on one day and sell it on a later day. Return the largest profit you can make, or 0 when every possible trade loses money.

Function

maxProfit(prices: integer-array) → integer

pricesinteger-array: the stock's price on each day, in order
Returnsinteger: the largest profit from one buy and a later sale, or 0

Constraints

1 ≤ prices.length ≤ 10⁵
0 ≤ prices[i] ≤ 10⁴
You make at most one trade, and you sell on a later day than you buy.

Examples

Input: prices = [7, 2, 5, 9, 1, 4]
Output: 7
Explanation: Buy on day 1 at 2 and sell on day 3 at 9 for a profit of 7. The cheapest price, 1 on day 4, comes after the 9, so the best sale after it earns only 3.

Follow-up

What if you may make as many trades as you like, while holding at most one share at a time?

Solution

You must buy before you sell, so the answer is not the highest price minus the lowest one. For each day you could sell, the best purchase is the cheapest day before it. Keeping that cheapest price as you walk forward turns the problem into a single pass.

Try every buy and sell pair

Correct, but does not finish on the largest tests

Intuition

Every trade is a buying day and a later selling day, so try every pair and keep the largest difference. Starting the best profit at 0 covers the choice not to trade. Every allowed trade gets checked, so the answer is correct.

A list of n prices has about n²/2 pairs: 100,000 days means about 5 billion subtractions.

Algorithm

Set best to 0.
Loop over every buying day buy.
For each one, loop over every selling day sell after it.
Compute prices[sell] minus prices[buy], and store it in best if it is larger.
Return best.

def maxProfit(prices):
    best = 0
    n = len(prices)
    for buy in range(n):
        for sell in range(buy + 1, n):
            best = max(best, prices[sell] - prices[buy])
    return best

One pass with the lowest price so far

Intuition

Fix the selling day i. The best day to have bought is the cheapest day up to i, so the best trade ending on day i earns prices[i] minus the lowest price so far. Every selling day gets paired with its best buying day, so the largest of those profits is the answer. On a day that sets a new low the profit is 0, the same as not trading.

The walk reads each price once and keeps two numbers, lowest and best: O(n) time and O(1) space.

Algorithm

Set lowest to the first price and best to 0.
Go through the prices in order.
If the current price is below lowest, make it the new lowest.
Compute the current price minus lowest, and store it in best if it is larger.
Return best.

def maxProfit(prices):
    lowest = prices[0]
    best = 0
    for price in prices:
        if price < lowest:
            lowest = price
        elif price - lowest > best:
            best = price - lowest
    return best

Pitfalls and edge cases

Returning the highest price minus the lowest price. In [7, 2, 5, 9, 1, 4] that gives 8, but the 1 comes after the 9. The answer is 7.
Letting the answer go negative. In [9, 7, 4, 3, 1] the best difference is -1; start best at 0, not at the first difference.
Starting lowest at 0. Every profit then equals the price itself, so [9, 7, 4, 3, 1] returns 9. Start it at the first price.

Frequently asked questions3

What is the time complexity of Best Time to Buy and Sell Stock?

The one-pass solution takes O(n) time for n days, because it reads each price once, and O(1) extra space: the lowest price so far and the best profit. Trying every pair of days takes O(n²) time.

Why not subtract the lowest price from the highest price?

The lowest price may come after the highest one, and you must buy before you sell. In [7, 2, 5, 9, 1, 4] the 1 comes after the 9, so the best allowed trade buys at 2 and sells at 9 for 7.

Is Best Time to Buy and Sell Stock a dynamic programming problem?

You can read it either way. The lowest price so far is a small piece of state you update each day, which is the dynamic programming view. Pairing each sale with the cheapest earlier day is the greedy view. Both lead to the same one-pass code.

def maxProfit(prices):
    # Write code here

Test #1

Test #2

Argument

prices = [7, 2, 5, 9, 1, 4]

Expected Output