Solution Approach
Solution Overview
There are 3 main approaches to solve this problem:
- One-Pass Approach - Complex approach
- Kadane's Algorithm Approach - Complex approach
- Brute Force Approach - Complex approach
Approach 1: One-Pass Approach
The key insight for solving this problem efficiently is to track the minimum price seen so far and calculate the potential profit if we sell at the current price.
As we iterate through the array, we update the minimum price if we find a lower price, and we update the maximum profit if selling at the current price would yield a higher profit.
This approach allows us to find the maximum profit in a single pass through the array, with O(n) time complexity and O(1) space complexity.
Algorithm:
- Initialize minPrice to infinity (or the maximum possible value) and maxProfit to 0.
- Iterate through each price in the array:
- a. Update minPrice to the minimum of minPrice and the current price.
- b. Calculate the potential profit if we sell at the current price: currentProfit = currentPrice - minPrice.
- c. Update maxProfit to the maximum of maxProfit and currentProfit.
- Return maxProfit as the result.
Time Complexity:
Where n is the length of the prices array. We iterate through the array once, performing constant-time operations at each step.
Space Complexity:
We only use a constant amount of extra space regardless of the input size.
Approach 2: Kadane's Algorithm Approach
Another way to think about this problem is in terms of daily price changes. We can transform the problem into finding the maximum subarray sum of the differences between consecutive prices.
This approach is based on Kadane's algorithm, which is used to find the maximum subarray sum. However, in this case, we have the additional constraint that we can only buy once and sell once, and we must buy before selling.
By tracking the maximum profit ending at each position, we can find the overall maximum profit in a single pass through the array.
Algorithm:
- Initialize maxCurr (maximum profit ending at current position) to 0 and maxSoFar (maximum profit found so far) to 0.
- Iterate through the array starting from the second element (i = 1):
- a. Calculate the price difference: diff = prices[i] - prices[i-1].
- b. Update maxCurr to the maximum of 0 and maxCurr + diff.
- c. Update maxSoFar to the maximum of maxSoFar and maxCurr.
- Return maxSoFar as the result.
Time Complexity:
Where n is the length of the prices array. We iterate through the array once, performing constant-time operations at each step.
Space Complexity:
We only use a constant amount of extra space regardless of the input size.
Approach 3: Brute Force Approach
The brute force approach is to consider all possible pairs of buy and sell days, where the buy day comes before the sell day, and find the pair that maximizes the profit.
While this approach is straightforward to understand, it has a time complexity of O(n²), which is inefficient for large inputs. However, it's worth mentioning as a baseline solution.
Algorithm:
- Initialize maxProfit to 0.
- Use nested loops to consider all possible pairs of buy and sell days:
- a. Outer loop (i) from 0 to n-2 represents the buy day.
- b. Inner loop (j) from i+1 to n-1 represents the sell day.
- c. Calculate the profit: profit = prices[j] - prices[i].
- d. Update maxProfit to the maximum of maxProfit and profit.
- Return maxProfit as the result.
Time Complexity:
Where n is the length of the prices array. We consider all possible pairs of buy and sell days, which is O(n²).
Space Complexity:
We only use a constant amount of extra space regardless of the input size.
Pseudocode
12345678910function maxProfit(prices): minPrice = Infinity maxProfit = 0 for price in prices: minPrice = min(minPrice, price) currentProfit = price - minPrice maxProfit = max(maxProfit, currentProfit) return maxProfitString Problems
Learning Objective
Understand different approaches to solve the stock profit maximizer problem and analyze their efficiency.
Solution Approaches
Approach 1: One-Pass Approach
The key insight for solving this problem efficiently is to track the minimum price seen so far and calculate the potential profit if we sell at the current price.
As we iterate through the array, we update the minimum price if we find a lower price, and we update the maximum profit if selling at the current price would yield a higher profit.
This approach allows us to find the maximum profit in a single pass through the array, with O(n) time complexity and O(1) space complexity.
Algorithm:
- Initialize minPrice to infinity (or the maximum possible value) and maxProfit to 0.
- Iterate through each price in the array:
- a. Update minPrice to the minimum of minPrice and the current price.
- b. Calculate the potential profit if we sell at the current price: currentProfit = currentPrice - minPrice.
- c. Update maxProfit to the maximum of maxProfit and currentProfit.
- Return maxProfit as the result.
Approach 2: Kadane's Algorithm Approach
Another way to think about this problem is in terms of daily price changes. We can transform the problem into finding the maximum subarray sum of the differences between consecutive prices.
This approach is based on Kadane's algorithm, which is used to find the maximum subarray sum. However, in this case, we have the additional constraint that we can only buy once and sell once, and we must buy before selling.
By tracking the maximum profit ending at each position, we can find the overall maximum profit in a single pass through the array.
Algorithm:
- Initialize maxCurr (maximum profit ending at current position) to 0 and maxSoFar (maximum profit found so far) to 0.
- Iterate through the array starting from the second element (i = 1):
- a. Calculate the price difference: diff = prices[i] - prices[i-1].
- b. Update maxCurr to the maximum of 0 and maxCurr + diff.
- c. Update maxSoFar to the maximum of maxSoFar and maxCurr.
- Return maxSoFar as the result.
Approach 3: Brute Force Approach
The brute force approach is to consider all possible pairs of buy and sell days, where the buy day comes before the sell day, and find the pair that maximizes the profit.
While this approach is straightforward to understand, it has a time complexity of O(n²), which is inefficient for large inputs. However, it's worth mentioning as a baseline solution.
Algorithm:
- Initialize maxProfit to 0.
- Use nested loops to consider all possible pairs of buy and sell days:
- a. Outer loop (i) from 0 to n-2 represents the buy day.
- b. Inner loop (j) from i+1 to n-1 represents the sell day.
- c. Calculate the profit: profit = prices[j] - prices[i].
- d. Update maxProfit to the maximum of maxProfit and profit.
- Return maxProfit as the result.
Complexity Analysis
One-Pass Approach Approach
Time Complexity
Where n is the length of the prices array. We iterate through the array once, performing constant-time operations at each step.
Space Complexity
We only use a constant amount of extra space regardless of the input size.
Kadane's Algorithm Approach Approach
Time Complexity
Where n is the length of the prices array. We iterate through the array once, performing constant-time operations at each step.
Space Complexity
We only use a constant amount of extra space regardless of the input size.
Brute Force Approach Approach
Time Complexity
Where n is the length of the prices array. We consider all possible pairs of buy and sell days, which is O(n²).
Space Complexity
We only use a constant amount of extra space regardless of the input size.
Pseudocode
One-Pass Approach Approach
12345678910function maxProfit(prices): minPrice = Infinity maxProfit = 0 for price in prices: minPrice = min(minPrice, price) currentProfit = price - minPrice maxProfit = max(maxProfit, currentProfit) return maxProfitKadane's Algorithm Approach Approach
12345678910111213function maxProfit(prices): if length of prices < 2: return 0 maxCurr = 0 maxSoFar = 0 for i from 1 to length of prices - 1: diff = prices[i] - prices[i-1] maxCurr = max(0, maxCurr + diff) maxSoFar = max(maxSoFar, maxCurr) return maxSoFar