121. Best Time to Buy and Sell Stock
121. Best Time to Buy and Sell Stock
Summary
You are given an array prices where prices[i] is the price of a 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 that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Approach
Use a prefix-minimum-style approach.
For each day, compare the current price with the minimum price seen so far. The profit on that day is current price - minimum past price, and the answer is the maximum such profit.
Function
Initialization:
min_price = prices[0]best = 0
For each price p in prices:
best = max(best, p - min_price)- min_price = min(min_price, p)
Return best.
Complexity
Time complexity: O(N)
Space complexity: O(1)