We can use a Greedy algorithm. Since we can make as many transactions as we want (but only hold one stock at a time), we can just capture every single upward price movement. If the price tomorrow is higher than today, we ‘buy’ today and ‘sell’ tomorrow.
// Pseudocode: Use recursion/DFS to try all possible buy/sell combinations.
// Too slow, O(2^n).// Pseudocode:
// 1. Init profit = 0.
// 2. Loop i from 1 to prices.size() - 1:
// 3. If prices[i] > prices[i-1]:
// 4. profit += prices[i] - prices[i-1]
// 5. Return profit.
class Solution {
public:
int maxProfit(vector<int>& prices) {
int profit = 0;
for (int i = 1; i < prices.size(); i++) {
if (prices[i] > prices[i-1]) {
profit += prices[i] - prices[i-1];
}
}
return profit;
}
};Time: O(n) for a single pass. Space: O(1) since we only use a single variable.
- Prices are strictly decreasing. We never add to profit, returns 0.
- Prices are strictly increasing. We capture the difference at every step, which equals
last_price - first_price.
The realization here is that multiple overlapping transactions on a continuous upward trend sum up to the total difference between the start and end of that trend. A very simple greedy strategy solves this perfectly.