Approach 1: Brute Force
- Try every possible buy day.
- For each buy day, try every sell day after it.
- Calculate profit and keep maximum.
class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
int profit = prices[j] - prices[i];
maxProfit = Math.max(maxProfit, profit);
}
}
return maxProfit;
}
}
Complexity
Time: O(n²)
Space: O(1)
Approach 2: Optimal One Pass
- Keep track of minimum price seen so far.
-
At every index:
- Calculate profit if sold today.
- Update maximum profit.
If current price is smaller, update minimum buy price.
Example:
Buy at 1
Sell at 6
Profit = 5
class Solution {
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;
}
}
Complexity
Time: O(n)
Space: O(1)