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 one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price=1), sell on day 5 (price=6), profit=5.
Example 2
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: No transaction gives profit.
1 <= prices.length <= 10^50 <= prices[i] <= 10^4Track the minimum price seen so far and the maximum profit.
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price; // found a cheaper buy day
} else {
maxProfit = Math.max(maxProfit, price - minPrice);
}
}
return maxProfit;
}Time: O(n) · Space: O(1)