We can use a Two Pointer / sliding window approach. We want to find a maximum difference where the smaller number comes before the larger number. We keep track of the minimum price seen so far and calculate the potential profit if we sold at the current price.
// Pseudocode: Try every pair of buy and sell days.
// 1. Init max_profit = 0.
// 2. For i from 0 to n-1:
// 3. For j from i+1 to n-1:
// 4. max_profit = max(max_profit, prices[j] - prices[i])
class Solution {
public:
int maxProfit(vector<int>& prices) {
int max_profit = 0;
for (int i = 0; i < prices.size(); i++) {
for (int j = i + 1; j < prices.size(); j++) {
max_profit = max(max_profit, prices[j] - prices[i]);
}
}
return max_profit;
}
};// Pseudocode:
// 1. Init min_price = INT_MAX, max_profit = 0.
// 2. For each price in prices:
// 3. min_price = min(min_price, price)
// 4. max_profit = max(max_profit, price - min_price)
// 5. Return max_profit.
class Solution {
public:
int maxProfit(vector<int>& prices) {
int min_price = INT_MAX;
int max_profit = 0;
for (int price : prices) {
if (price < min_price) {
min_price = price;
} else if (price - min_price > max_profit) {
max_profit = price - min_price;
}
}
return max_profit;
}
};Time: O(n) because we pass through the array once. Space: O(1) as we only use two variables.
- Array is in descending order. Minimum price is constantly updated, but
price - min_priceis never positive. Returns 0.
This is a classic ‘minimum so far’ pattern. Whenever you need to find a maximum difference with a temporal ordering (buy before sell), tracking the minimum value seen so far is often the key.