Problem
You are given an integer array prices, where prices[i] represents the stock price on the ith day. You may buy and sell the stock multiple times, but you must sell the stock before buying it again.Return the maximum profit that can be achieved. If no profit is possible, return 0.
Example
Consider the following example to understand the expected input and output.Input
prices = [7,1,5,3,6,4]Output
7Solution
The key idea is to take advantage of every profitable price increase. Unlike the previous problem, we are allowed to make multiple transactions, so we do not need to find one single buy and sell pair.For each day, if the current price is greater than the previous day's price, we can consider the increase as a profit and add it to the total. This effectively captures every upward movement in the stock price.
If the current price is lower than or equal to the previous day's price, there is no profit to be made from that movement, so we simply move to the next day.
public int maxProfit(int[] prices) {
// Handle null or empty input.
if (prices == null || prices.length == 0) {
return 0;
}
int max = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
// Add the profit from the current price increase.
max += prices[i] - prices[i - 1];
}
}
return max;
}Complexity
The array is traversed only once, and each element is processed exactly once. Therefore, the time complexity is O(n).The algorithm uses only one variable to store the total profit, so the extra space complexity is O(1).
