You are given an array
prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy and a single day in the future to sell. Return the maximum profit you can achieve from this transaction. If no profit is possible, return 0.Example
prices = [7, 1, 5, 3, 6, 4]
Output: 5
Buy on day 1 (price = 1) and sell on day 4 (price = 6) for a profit of 6 - 1 = 5.
Keep track of the minimum price you've seen so far as you scan left to right. At each day, calculate the profit you'd make if you sold today (current price minus the minimum so far). The answer is the maximum of all these potential profits.
Why this works
You must buy before you sell, so scan left to right. At every position, the best you can do is sell at today’s price after buying at the cheapest price you’ve seen so far. By tracking the running minimum, you compute the optimal profit in a single pass.
Step by step
- Initialize trackers — set min price to infinity and max profit to 0.
- Update the minimum — at each day, check if today’s price is the new cheapest.
- Calculate potential profit — subtract the min price from today’s price; if it beats the current best, update max profit.
Time: O(n)
Space: O(1)
class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
minPrice = Math.min(minPrice, price); // track cheapest buy so far
maxProfit = Math.max(maxProfit, price - minPrice); // best profit if we sell today
}
return maxProfit;
}
}
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minPrice = INT_MAX;
int maxProfit = 0;
for (int price : prices) {
minPrice = min(minPrice, price); // track cheapest buy so far
maxProfit = max(maxProfit, price - minPrice); // best profit if we sell today
}
return maxProfit;
}
};
def maxProfit(prices: list[int]) -> int:
min_price = float('inf')
max_profit = 0
for price in prices:
min_price = min(min_price, price) # track cheapest buy so far
max_profit = max(max_profit, price - min_price) # best profit if we sell today
return max_profit