You are given an array prices where prices[i] is the price of a given stock on the ith…
- User
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete at most two transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3. Example 2:
Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again. Example 3:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.
Constraints:
1 <= prices.length <= 105 0 <= prices[i] <= 105 solve this code for me
- Assistant
The problem asks us to find the maximum profit achievable by completing at most two transactions. We cannot engage in multiple transactions simultaneously, meaning a stock must be sold before another can be bought.
This problem can be efficiently solved using dynamic programming. Since we are allowed at most two transactions, we can keep track of the maximum profit at different stages of these transactions.
Let's define four variables to represent the maximum profit at different states:
t1_buy: The maximum profit (or minimum cost) after completing the first buy operation. Since we are buying, this will be a negative number, representing the money spent. We want this value to be as high as possible (closest to zero, meaning cheapest buy).t1_sell: The maximum profit after completing the first sell operation. This implies we have completed one full transaction (buy then sell).t2_buy: The maximum profit after completing the second buy operation. This means we have completed the first transaction and then bought a second stock. This value will be(profit from 1st transaction - cost of 2nd stock).t2_sell: The maximum profit after completing the second sell operation. This implies we have completed two full transactions.
Initialization:
t1_buy: Initially, we haven't bought anything. If we buy on day 0, the cost is-prices[0]. So, we can initialize it to-prices[0]. (Alternatively,float('-inf')and handle the first day in the loop, but-prices[0]works fine for the first possible buy.)t1_sell: Initially, no transactions are complete, so the profit is0.t2_buy: We cannot buy a second stock before selling the first. So, this state is initially impossible or yields a very poor profit. Initialize withfloat('-inf').t2_sell: Initially, no second transaction is complete, so the profit is0.
Iteration (for each price
pinprices):We iterate through the
pricesarray. For each day'sprice, we update our state variables. The order of updates is crucial to ensure that we use values from the "previous day" and respect the "sell before buy" rule. By updating from the highest transaction level (t2_sell) down to the lowest (t1_buy), we ensure that when a state (e.g.,t2_buy) depends on a previous state (e.g.,t1_sell), it uses thet1_sellvalue calculated from the previous day's price, not thet1_sellvalue updated with the current day's price.For each
price:-
t2_sell = max(t2_sell, t2_buy + price):t2_sell(old value): Represents the max profit from selling the second stock up to the previous day.t2_buy + price: Represents the profit if we sell the second stock today (using the maximum profit from having bought the second stock up to the previous day,t2_buy, plus the currentprice).- We take the maximum of these two options.
-
t2_buy = max(t2_buy, t1_sell - price):t2_buy(old value): Represents the max profit from buying the second stock up to the previous day.t1_sell - price: Represents the profit if we buy the second stock today (using the max profit from having sold the first stock up to the previous day,t1_sell, minus the currentpriceof buying).- We take the maximum of these two options.
-
t1_sell = max(t1_sell, t1_buy + price):t1_sell(old value): Max profit from selling the first stock up to the previous day.t1_buy + price: Profit if we sell the first stock today (using the max profit from having bought the first stock up to the previous day,t1_buy, plus the currentprice).- We take the maximum of these two options.
-
t1_buy = max(t1_buy, -price):t1_buy(old value): Max profit from buying the first stock up to the previous day.-price: Profit if we buy the first stock today (current cost).- We take the maximum of these two options (i.e., choose the buy point that results in the highest remaining capital or least cost).
Final Result:
The problem asks for the maximum profit with at most two transactions. This means 0, 1, or 2 transactions are allowed.
t1_sellwill store the maximum profit after completing at most one transaction.t2_sellwill store the maximum profit after completing at most two transactions. Since botht1_sellandt2_sellare initialized to0and only track non-negative profits (a profit of 0 is achieved by doing nothing), the overall maximum profit will bemax(t1_sell, t2_sell).
Example Walkthrough (
prices = [3,3,5,0,0,3,1,4]):Initial (Day 0,
price = 3):t1_buy = -3,t1_sell = 0,t2_buy = -inf,t2_sell = 0Day 1 (
price = 3):t2_sell = max(0, -inf + 3) = 0t2_buy = max(-inf, 0 - 3) = -3t1_sell = max(0, -3 + 3) = 0t1_buy = max(-3, -3) = -3State:t1_buy=-3, t1_sell=0, t2_buy=-3, t2_sell=0Day 2 (
price = 5):t2_sell = max(0, -3 + 5) = 2t2_buy = max(-3, 0 - 5) = -3t1_sell = max(0, -3 + 5) = 2t1_buy = max(-3, -5) = -3State:t1_buy=-3, t1_sell=2, t2_buy=-3, t2_sell=2Day 3 (
price = 0):t2_sell = max(2, -3 + 0) = 2t2_buy = max(-3, 2 - 0) = 2(Optimal to buy 2nd stock now, after selling 1st at 5)t1_sell = max(2, -3 + 0) = 2t1_buy = max(-3, -0) = 0(Optimal to buy 1st stock now at 0) State:t1_buy=0, t1_sell=2, t2_buy=2, t2_sell=2Day 4 (
price = 0):t2_sell = max(2, 2 + 0) = 2t2_buy = max(2, 2 - 0) = 2t1_sell = max(2, 0 + 0) = 2t1_buy = max(0, -0) = 0State:t1_buy=0, t1_sell=2, t2_buy=2, t2_sell=2Day 5 (
price = 3):t2_sell = max(2, 2 + 3) = 5t2_buy = max(2, 2 - 3) = 2t1_sell = max(2, 0 + 3) = 3t1_buy = max(0, -3) = 0State:t1_buy=0, t1_sell=3, t2_buy=2, t2_sell=5Day 6 (
price = 1):t2_sell = max(5, 2 + 1) = 5t2_buy = max(2, 3 - 1) = 2t1_sell = max(3, 0 + 1) = 3t1_buy = max(0, -1) = 0State:t1_buy=0, t1_sell=3, t2_buy=2, t2_sell=5Day 7 (
price = 4):t2_sell = max(5, 2 + 4) = 6t2_buy = max(2, 3 - 4) = 2t1_sell = max(3, 0 + 4) = 4t1_buy = max(0, -4) = 0State:t1_buy=0, t1_sell=4, t2_buy=2, t2_sell=6Final result:
max(t1_sell, t2_sell) = max(4, 6) = 6.Complexity Analysis:
- Time Complexity: O(N), where N is the number of days (length of
prices). We iterate through thepricesarray once. - Space Complexity: O(1), as we only use a constant number of variables to store the state.
import math class Solution: def maxProfit(self, prices: list[int]) -> int: n = len(prices) if n < 2: return 0 # t1_buy: max profit after the first buy (or min cost to hold the first stock) # Initialize with the cost of buying on day 0 t1_buy = -prices[0] # t1_sell: max profit after the first sell # Initialize to 0, as no transaction has completed yet t1_sell = 0 # t2_buy: max profit after the second buy # Initialize to negative infinity, as it's impossible to buy a second stock before any sell t2_buy = float('-inf') # t2_sell: max profit after the second sell # Initialize to 0, as no second transaction has completed yet t2_sell = 0 # Iterate through prices starting from the second day (index 1) for i in range(1, n): price = prices[i] # Update t2_sell: # Option 1: Do not sell second stock today, retain previous max profit. # Option 2: Sell second stock today. Requires having bought second stock (t2_buy) + current price. t2_sell = max(t2_sell, t2_buy + price) # Update t2_buy: # Option 1: Do not buy second stock today, retain previous max profit. # Option 2: Buy second stock today. Requires having sold first stock (t1_sell) - current price. t2_buy = max(t2_buy, t1_sell - price) # Update t1_sell: # Option 1: Do not sell first stock today, retain previous max profit. # Option 2: Sell first stock today. Requires having bought first stock (t1_buy) + current price. t1_sell = max(t1_sell, t1_buy + price) # Update t1_buy: # Option 1: Do not buy first stock today, retain previous max profit. # Option 2: Buy first stock today (cost is -price). t1_buy = max(t1_buy, -price) # The maximum profit can be from completing one transaction or two transactions. # t1_sell stores the max profit from at most one transaction. # t2_sell stores the max profit from at most two transactions. # Since '0' profit is always an option (doing nothing), and t1_sell/t2_sell are initialized to 0, # they will correctly hold non-negative max profits. return max(t1_sell, t2_sell)
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.