Best Time to Buy and Sell Stock III
You are given an array of integers representing the daily stock prices. You can buy and sell the stock at most twice. Find the maximum possible profit.
Constraints:
- 1 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^5
Examples:
Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price=0) and sell on day 6 (price=4), then buy on day 7 (price=1) and sell on day 8 (price=4). The total profit is 4 + 2 = 6.
Solutions
Dynamic Programming
Time: O(n)Space: O(1)
We use four variables to keep track of the maximum profit after the first buy, first sell, second buy, and second sell. We iterate through the prices and update these variables accordingly.
public int maxProfit(int[] prices) {
int buy1 = Integer.MIN_VALUE, sell1 = 0, buy2 = Integer.MIN_VALUE, sell2 = 0;
for (int price : prices) {
buy1 = Math.max(buy1, -price);
sell1 = Math.max(sell1, buy1 + price);
buy2 = Math.max(buy2, sell1 - price);
sell2 = Math.max(sell2, buy2 + price);
}
return sell2;
}Follow-up:
What if you can buy and sell the stock at most k times?
