You are given an array prices where prices[i] is the price of a given stock on the i-th day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Examples
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Constraints
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4
Prerequisites
Sliding windows — a left and right edge moving forward only, and the invariant that decides when the left edge advances. Hash maps or fixed-size counts for what the window currently holds.
How to think about it
1. Track the Cheapest Day So Far Optimal
Intuition
Selling on day i earns today's price minus the cheapest day before it — so only one number from the past matters. Carry the minimum seen so far, and every day answers in constant time. That reframing, from "which pair" to "what do I need from the past", is the whole lesson.
Algorithm
1. Track the lowest price seen so far and the best profit so far. 2. On each day, the profit is today's price minus that lowest price. 3. Keep the better profit, then update the lowest price. 4. Never-profitable inputs leave the profit at zero, which is the right answer.