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) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Time Complexity: O(n)
Space Complexity: O(1)
We iterate through the array of prices while keeping track of the minimum price seen so far. At each step, we calculate the potential profit if we sold at the current price (current price - min price). We update the maximum profit if the potential profit is greater than what we've seen before.
This is effectively a greedy approach or a dynamic sliding window where the left boundary (buy day) jumps to the current day if the current price is lower than the current buy price.
int maxProfit(vector<int>& prices) {
int minPrice = INT_MAX;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price; // Found a new lowest price to buy
} else {
maxProfit = max(maxProfit, price - minPrice); // Check profit if sold today
}
}
return maxProfit;
}Time Complexity: O(n²)
Space Complexity: O(1)
Check every pair of days (i, j) where i < j and find the maximum difference.
- We only care about the lowest price in the past relative to the current day.
- We don't need to know which day we bought or sold, just the prices.
- This is a classic "maximum subarray sum" variation (Kadane's Algorithm concept can also be applied to differences).
- 122. Best Time to Buy and Sell Stock II (Multiple transactions)
- 53. Maximum Subarray