Compute max profit with two transactions
Hard
Java
Variables
24 views
Problem Statement
Task: return max profit with at most 2 buy-sell transactions. Use variables for DP states.
Input Format
• First line: Integer n (number of days)
• Second line: n space-separated integers (stock prices)
• Second line: n space-separated integers (stock prices)
Output Format
• Print one integer: maximum profit
Example
6 3 3 5 0 0 3
123
Constraints
• 1 ≤ n ≤ 10^5
• 0 ≤ prices[i] ≤ 10^9
• At most 2 transactions allowed
• You must sell before buying again
• 0 ≤ prices[i] ≤ 10^9
• At most 2 transactions allowed
• You must sell before buying again
Concept Explanation
Prices: 3 3 5 0 0 3
Best strategy:
• Buy at 3, Sell at 5 → Profit = 2
• Buy at 0, Sell at 3 → Profit = 3
Total Profit = 2 + 3 = 5
Best strategy:
• Buy at 3, Sell at 5 → Profit = 2
• Buy at 0, Sell at 3 → Profit = 3
Total Profit = 2 + 3 = 5
Step-by-Step Explanation
We maintain 4 variables:
• buy1 → Maximum profit after first buy
• sell1 → Maximum profit after first sell
• buy2 → Maximum profit after second buy
• sell2 → Maximum profit after second sell
Steps:
1.Initialize:
• buy1 = -prices[0]
• sell1 = 0
• buy2 = -prices[0]
• sell2 = 0
2.For each price:
• buy1 = max(buy1, -price)
• sell1 = max(sell1, buy1 + price)
• buy2 = max(buy2, sell1 - price)
• sell2 = max(sell2, buy2 + price)
3.After processing all prices,
• Return sell2 as final maximum profit.
• buy1 → Maximum profit after first buy
• sell1 → Maximum profit after first sell
• buy2 → Maximum profit after second buy
• sell2 → Maximum profit after second sell
Steps:
1.Initialize:
• buy1 = -prices[0]
• sell1 = 0
• buy2 = -prices[0]
• sell2 = 0
2.For each price:
• buy1 = max(buy1, -price)
• sell1 = max(sell1, buy1 + price)
• buy2 = max(buy2, sell1 - price)
• sell2 = max(sell2, buy2 + price)
3.After processing all prices,
• Return sell2 as final maximum profit.
Concept Explanation
Prices: 3 3 5 0 0 3
Best strategy:
• Buy at 3, Sell at 5 → Profit = 2
• Buy at 0, Sell at 3 → Profit = 3
Total Profit = 2 + 3 = 5
Best strategy:
• Buy at 3, Sell at 5 → Profit = 2
• Buy at 0, Sell at 3 → Profit = 3
Total Profit = 2 + 3 = 5
Step-by-Step Explanation
We maintain 4 variables:
• buy1 → Maximum profit after first buy
• sell1 → Maximum profit after first sell
• buy2 → Maximum profit after second buy
• sell2 → Maximum profit after second sell
Steps:
1.Initialize:
• buy1 = -prices[0]
• sell1 = 0
• buy2 = -prices[0]
• sell2 = 0
2.For each price:
• buy1 = max(buy1, -price)
• sell1 = max(sell1, buy1 + price)
• buy2 = max(buy2, sell1 - price)
• sell2 = max(sell2, buy2 + price)
3.After processing all prices,
• Return sell2 as final maximum profit.
• buy1 → Maximum profit after first buy
• sell1 → Maximum profit after first sell
• buy2 → Maximum profit after second buy
• sell2 → Maximum profit after second sell
Steps:
1.Initialize:
• buy1 = -prices[0]
• sell1 = 0
• buy2 = -prices[0]
• sell2 = 0
2.For each price:
• buy1 = max(buy1, -price)
• sell1 = max(sell1, buy1 + price)
• buy2 = max(buy2, sell1 - price)
• sell2 = max(sell2, buy2 + price)
3.After processing all prices,
• Return sell2 as final maximum profit.
Input / Output Format
Input Format
• First line: Integer n (number of days)
• Second line: n space-separated integers (stock prices)
• Second line: n space-separated integers (stock prices)
Output Format
• Print one integer: maximum profit
Constraints
• 1 ≤ n ≤ 10^5
• 0 ≤ prices[i] ≤ 10^9
• At most 2 transactions allowed
• You must sell before buying again
• 0 ≤ prices[i] ≤ 10^9
• At most 2 transactions allowed
• You must sell before buying again
Examples
Input:
6
3 3 5 0 0 3
Output:
123
Example Solution (Public)
static int maxProfit2(int[] p){int buy1=Integer.MIN_VALUE,buy2=Integer.MIN_VALUE;int sell1=0,sell2=0;for(int x:p){buy1=Math.max(buy1,-x);sell1=Math.max(sell1,buy1+x);buy2=Math.max(buy2,sell1-x);sell2=Math.max(sell2,buy2+x);}return sell2;}
Official Solution Code
static int maxProfit2(int[] p){int buy1=Integer.MIN_VALUE,buy2=Integer.MIN_VALUE;int sell1=0,sell2=0;for(int x:p){buy1=Math.max(buy1,-x);sell1=Math.max(sell1,buy1+x);buy2=Math.max(buy2,sell1-x);sell2=Math.max(sell2,buy2+x);}return sell2;}
Please login to submit solutions.