Problem statement

You are given an array prices where prices[i] is the price of a stock on day i.

You want to maximize profit by choosing one day to buy and a later day to sell. Return the maximum profit; if no profit is possible, return 0.

Example 1

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price 1), sell on day 5 (price 6): 6 - 1 = 5.

Example 2

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: Prices only fall — no profitable transaction exists.

Constraints

• 1 <= prices.length <= 30
• 0 <= prices[i] <= 1000

Hints for Best Time to Buy and Sell Stock

1. Hint 1

   Track the lowest price seen so far while scanning left to right.

2. Hint 2

   At each day, the best sale ending here is price - minSoFar.

How to solve Best Time to Buy and Sell Stock

For any chosen sell day, the best possible buy is the cheapest price seen before it. So sweep once, carrying the minimum price so far, and at each day ask what profit selling today would give. The largest of those is the answer.

Approach

1. Track minPrice, initially the first day's price, and best, initially 0.
2. For each later day, compute price - minPrice and update best if it is larger.
3. Then update minPrice if today's price is lower.
4. Return best.

Why it works

Every valid transaction is determined by its sell day, and for a fixed sell day the profit is maximised by the smallest price strictly before it — which is exactly what minPrice holds when the day is examined. Taking the maximum over all sell days therefore covers every transaction once. Updating minPrice after computing the profit is what enforces "buy before sell": a single day can never be both.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Seed the profit at 0, not at a negative sentinel — no transaction is always allowed, so a falling market answers 0.
• Update the running minimum after taking the profit, or you allow buying and selling on the same day.
• This is the single-transaction problem; summing every upward step solves the unlimited-transactions variant instead.

Reference solution

Python

from typing import List

def maxProfit(prices: List[int]) -> int:
    lo = float("inf")
    best = 0
    for p in prices:
        lo = min(lo, p)
        best = max(best, p - lo)
    return best

Java

public static int maxProfit(int[] prices) {
    int minPrice = prices[0], best = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] - minPrice > best) best = prices[i] - minPrice;
        if (prices[i] < minPrice) minPrice = prices[i];
    }
    return best;
}

C++

int maxProfit(vector<int>& prices) {
    int minPrice = prices[0], best = 0;
    for (int i = 1; i < (int) prices.size(); i++) {
        if (prices[i] - minPrice > best) best = prices[i] - minPrice;
        if (prices[i] < minPrice) minPrice = prices[i];
    }
    return best;
}

JavaScript

var maxProfit = function(prices) {
    let lo = Infinity, best = 0;
    for (const p of prices) {
        lo = Math.min(lo, p);
        best = Math.max(best, p - lo);
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy