Problem Description
Given an integer array prices, where prices[i] is the price of a stock on day i.
Every day you can decide to buy and/or sell a stock. You can hold at most one share of the stock at any time.
Find and return the maximum profit you can achieve.
Constraints
- The array can contain from
1to3 * 10⁴elements - Values are integers in the range from
0to10⁴
Examples
Input: [7,1,5,3,6,4]
Answer: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit is 5 - 1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit is 6 - 3 = 3. Total profit is 4 + 3 = 7.
Local minima and maxima approach
To maximize profit from stock trading, we need to buy at the lowest price and sell at the highest. This means we should buy at local minima and sell at local maxima.
Let's take the following array of prices in dollars [20, 10, 15, 5, 10, 20, 10] and represent it as a chart.
Now the chart clearly shows that we need to make two purchases and two sales:
- buy the stock on day 2 for 10 and sell on day 3 for 15
- buy the stock on day 4 for 5 and sell on day 6 for 20
As a result, we can achieve the maximum profit and earn $20.
Thus, the solution boils down to iterating through the entire array and finding local minima and local maxima. As soon as we encounter a minimum, we store the price on that day. As soon as we encounter a maximum, we calculate the difference between the last minimum and the maximum price and add it to our total profit.
Solution
export const maxProfitMinMax = (prices: number[]): number => {
let res = 0;
let min = prices[0];
let max = prices[0];
for (let i = 1; i < prices.length; i++) {
if (prices[i] > max) {
max = prices[i];
} else {
res += max - min;
min = prices[i];
max = prices[i];
}
}
res += max - min;
return res;
};Complexity Analysis
n — the number of elements in the array.
Time Complexity
The time complexity is O(n), since we iterate through all elements of the array.
Space Complexity
The space complexity is O(1), since we do not allocate any additional variables.
Ascending trends approach
If you look closely at the chart, you can notice that the maximum possible profit is the sum of the differences in stock prices between consecutive days on ascending trends.
This means we can greatly simplify the solution and avoid tracking local minima and maxima. We just need to find all ascending segments on the chart and sum up the price differences between consecutive days.
export const maxProfitTrends = (prices: number[]): number => {
let res = 0;
for (let i = 0; i < prices.length - 1; i++) {
if (prices[i] < prices[i + 1]) {
res += prices[i + 1] - prices[i];
}
}
return res;
};Complexity Analysis
n — the number of elements in the array.
Time Complexity
The time complexity is O(n), since we iterate through all elements of the array.
Space Complexity
The space complexity is O(1), since we do not allocate any additional variables.