To solve this problem, we need to determine the maximum profit that can be achieved by buying a stock at a lower price and selling it at a higher price later. The solution must be efficient, running in linear time to handle large input sizes.
Approach
The key insight here is to keep track of two values as we iterate through the array of stock prices:
- Minimum Price So Far: The lowest price encountered up to the current point. This helps us calculate the potential profit if we sell at the current price.
- Maximum Profit: The highest profit we can achieve by selling at the current price (using the minimum price so far) compared to the previous maximum profit.
Steps:
- If the array has fewer than 2 elements, return 0 (since we can't buy and sell).
- Initialize
minPriceto the first element of the array andmaxProfitto 0. - Iterate through the array starting from the second element:
- Calculate the current profit as the difference between the current price and
minPrice. - Update
maxProfitif the current profit is higher than the existingmaxProfit. - Update
minPriceif the current price is lower than the existingminPrice.
- Calculate the current profit as the difference between the current price and
- Return
maxProfit(this will be 0 if no profit is possible).
Solution Code
function getMaxProfit(prices) {
if (prices.length < 2) return 0;
let minPrice = prices[0];
let maxProfit = 0;
for (let i = 1; i < prices.length; i++) {
const currentPrice = prices[i];
const currentProfit = currentPrice - minPrice;
if (currentProfit > maxProfit) {
maxProfit = currentProfit;
}
if (currentPrice < minPrice) {
minPrice = currentPrice;
}
}
return maxProfit;
}
Explanation
- Efficiency: The algorithm runs in O(n) time complexity where n is the number of elements in the array. This is because we iterate through the array exactly once.
- Space Complexity: The space complexity is O(1) since we only use a few variables to track the minimum price and maximum profit.
Let’s test the solution against the example:
- Input:
[10,7,5,8,11,9] - Iteration steps:
minPrice =10,maxProfit=0→ next price 7: profit=-3 (no change), minPrice=7.- Next price5: profit=-2 (no change), minPrice=5.
- Next price8: profit=3 → maxProfit=3.
- Next price11: profit=6 → maxProfit=6.
- Next price9: profit=4 (no change).
- Output:
6(correct).
This approach efficiently handles all cases, including when prices are decreasing (returns 0) or increasing (returns the maximum possible profit). It’s optimal and works for large input sizes.
Answer: The function getMaxProfit as written above will return the correct maximum profit. For the example input, the output is 6. So the final answer is \boxed{6}.


作者声明:本文包含人工智能生成内容。