121. Best Time to Buy and Sell Stock
Intitution
To maximize profit, we want to buy at the lowest price and sell at the highest price after buying. So, while iterating through the array, we keep track of the minimum price seen so far, and at each step, calculate the profit if we sell at the current price. The answer will be the maximum of all such profits.
Complxity
Space Complexity
Time Complexity
Code
public int maxProfit(int[] prices) {
// Initialize the minimum price to the first day's price
int minPriceSoFar = prices[0];
// Initialize profit to 0 (no transaction yet)
int maxProfit = 0;
// Traverse the price array starting from the second day
for (int i = 1; i < prices.length; ++i) {
// Calculate the profit if sold today, and update maxProfit
maxProfit = Math.max(prices[i] - minPriceSoFar, maxProfit);
// Update the minimum price so far if today's price is lower
minPriceSoFar = Math.min(prices[i], minPriceSoFar);
}
// Return the maximum profit found
return maxProfit;
}
Last updated