Best Time to Buy and Sell Stock

prices[i] is a stock’s price on day i. You may buy once and sell once, on a later day. Return the maximum profit you can make, or 0 if no profitable trade exists.

Examples

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5        (buy at 1, sell at 6)

Input:  prices = [7, 6, 4, 3, 1]
Output: 0        (prices only fall)

Constraints

• 1 ≤ prices.length ≤ 10⁵, 0 ≤ prices[i] ≤ 10⁴

Explanation

Brute force — O(n²)

Try every buy day with every later sell day.

Optimal — one pass, O(n)

If you sell on day i, the best buy day is the cheapest day before it. So scan once, keeping the lowest price seen so far; at each day, the candidate profit is price − lowest. Track the maximum.

This is a sliding window where the left edge (buy day) jumps forward whenever a new minimum appears.

Complexity

• Time: O(n). Space: O(1).