Best Time to Buy and Sell Stock
Examples
Example 1:
Input: prices = [10,1,5,6,7,1]
Output: 6
Explanation:
Example 2:
Input: prices = [10,8,7,5,2]
Output: 0
Explanation:
Example 1:
Input: prices = [10,1,5,6,7,1]
Output: 6
Explanation:
Example 2:
Input: prices = [10,8,7,5,2]
Output: 0
Explanation:
You are given an integer array prices where prices[i] is the price of NeetCoin on the ith day.
You may choose a single day to buy one NeetCoin and choose a different day in the future to sell it.
Return the maximum profit you can achieve. You may choose to not make any transactions, in which case the profit would be 0.
Buy prices[1] and sell prices[4], profit = 7 - 1 = 6.
No profitable transactions can be made, thus the max profit is 0.
1 <= prices.length <= 1000 <= prices[i] <= 100Scan the prices once, tracking the minimum price seen so far. At each day, compute the profit if you sold today (current price minus min price) and update the best profit. This naturally returns 0 for strictly decreasing prices or when no transaction is beneficial.
The best profit for selling on day i must buy at the lowest price seen before i. By maintaining that minimum as we scan, we evaluate the optimal profit for every sell day and keep the maximum across all days.
O(n)O(1)class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_price = float('inf')
best = 0
for price in prices:
if price < min_price:
min_price = price
else:
best = max(best, price - min_price)
return best