You are given an array prices
where prices[i]
is the price of a given stock on the i
-th 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:
Input: [7,1,5,3,6,4]
Output: 5
(Buy on day 2 (price=1) and sell on day 5 (price=6), profit = 6-1 = 5)
Brute-Force Approach
The basic idea is simple: we will use two nested loops to go through each pair of days and calculate the difference between selling and buying prices.
We will update our maximum profit whenever we find a pair that gives us higher profit.
Java Code:
public class StockProfit {
public static 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];
if (profit > maxProfit) {
maxProfit = profit;
}
}
}
return maxProfit;
}
public static void main(String[] args) {
int[] prices = {7, 1, 5, 3, 6, 4};
int result = maxProfit(prices);
System.out.println("Maximum Profit: " + result); // Output will be 5
}
}
Complexity Analysis
- Time Complexity: O(n2) Because of two nested for loops.
- Space Complexity: O(1) No extra space used.
Optimal Approach
The optimal approach uses a single loop.
We keep track of the minimum price we’ve seen so far and the maximum profit we can make for each day, with that minimum price.
Java Code:
public class StockProfit {
public static int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] - minPrice > maxProfit) {
maxProfit = prices[i] - minPrice;
}
}
return maxProfit;
}
public static void main(String[] args) {
int[] prices = {7, 1, 5, 3, 6, 4};
int result = maxProfit(prices);
System.out.println("Maximum Profit: " + result); // Output will be 5
}
}
Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(1)
Summary
The brute-force approach works but is slow O(n2), making it impractical for large inputs.
The optimal approach gives us the same result much more efficiently O(n), and it only uses constant extra space.