Problem
Given an array of stock prices, find the maximum profit you can achieve from one buy and one sell. You must buy before you sell.
Example
Input: [7,1,5,3,6,4]
Output: 5
Buy at 1, sell at 6.Solution
Track the lowest price seen so far. At each day, compute potential profit if selling today.
def max_profit(prices):
min_price = float('inf')
max_profit = 0
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profitfunction maxProfit(prices) {
let minPrice = Infinity, maxProfit = 0;
for (const price of prices) {
if (price < minPrice) minPrice = price;
else if (price - minPrice > maxProfit) maxProfit = price - minPrice;
}
return maxProfit;
}int maxProfit(vector<int>& prices) {
int minPrice = INT_MAX, maxProfit = 0;
for (int price : prices) {
minPrice = min(minPrice, price);
maxProfit = max(maxProfit, price - minPrice);
}
return maxProfit;
}public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE, maxProfit = 0;
for (int price : prices) {
minPrice = Math.min(minPrice, price);
maxProfit = Math.max(maxProfit, price - minPrice);
}
return maxProfit;
}Complexity
- Time: O(n)
- Space: O(1)
Explanation
We don’t need to track when the lowest day was. Just maintain the running minimum and the best profit if we sold at the current day.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?