Best Time to Buy and Sell Stock
You are given an array of integers representing the daily stock prices. You can only buy and sell the stock once. The goal is to find the maximum possible profit.
Constraints:
- You must buy the stock before selling it
- You can only buy and sell the stock once
- You cannot buy and sell the stock on the same day
Examples:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price=1) and sell on day 5 (price=6), profit = 6-1 = 5
Solutions
One Pass
Time: O(n)Space: O(1)
We initialize two variables, minPrice and maxProfit. We iterate through the prices array, updating minPrice whenever we find a lower price. We then calculate the profit by subtracting minPrice from the current price and update maxProfit if the calculated profit is higher.
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
minPrice = Math.min(minPrice, price);
int profit = price - minPrice;
maxProfit = Math.max(maxProfit, profit);
}
return maxProfit;
}Follow-up:
What if you can buy and sell the stock multiple times?
