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.
def maxProfit(self, prices:
List[int]) -> int:
buy1, sell1, buy2, sell2 = -float('inf'), 0, -float('inf'), 0
for price in prices:
buy1 = max(buy1, -price)
sell1 = max(sell1, buy1 + price)
buy2 = max(buy2, sell1 - price)
sell2 = max(sell2, buy2 + price)
return sell2Follow-up:
What if you can buy and sell the stock at most k times?
