Intuition
The goal is to find the largest difference between two numbers in an array, with the constraint that the smaller number (buy price) must appear before the larger number (sell price).
A brute-force approach would be to check every possible pair of buy and sell days, but that would be too slow (O(N²)).
A much more efficient approach is to iterate through the prices just once. While we iterate, we maintain two key pieces of information:
- The lowest stock price seen so far (
min_price). This is the best day we could have possibly bought the stock up to the current day. - The maximum profit seen so far (
max_profit). This is the best profit we could have made.
For each day, we calculate the potential profit if we were to sell on that day: `current_price - min_price`. We then update our `max_profit` if this new profit is higher. Finally, we update `min_price` if the current day's price is a new low. This ensures we always know the best buying price for any future selling day.