Problem
You are given an integer array prices, where prices[i] is the price of a given stock on the ith day.Choose a single day to buy one stock and a different future day to sell that stock to maximize your profit. Return the maximum profit you can achieve. If no profit is possible, return 0.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
prices = [7,1,5,3,6,4] Output
5 Solution
This solution traverses the array once while keeping track of the lowest stock price seen so far.For each day's price, it calculates the profit that would be earned by selling the stock on that day after buying it at the lowest price seen so far.
If this profit is greater than the current maximum profit, the maximum profit is updated. The minimum price is also updated whenever a lower price is encountered.
By continuously tracking the lowest buying price and the best profit, we can find the maximum possible profit in a single traversal.
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
// Update the lowest buying price.
minPrice = Math.min(minPrice, price);
// Calculate and update the maximum profit.
maxProfit = Math.max(maxProfit, price - minPrice);
}
return maxProfit;
}
Complexity
The algorithm scans the array only once, processing each element exactly once. This results in a linear time complexity ofO(n). Only two variables are used to track the minimum price and maximum profit, so the extra space complexity is
O(1).