LeetCode - Best Time to Buy and Sell Stock III
Problem description
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
1
2
3
4
Input: [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:
1
2
3
4
5
Input: [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:
1
2
3
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Analysis
The first thought is to use two transaction like previous problems, find out all transactions and choose the max two. However, suppose we have a prices array with [1,2,4,2,5,7,2,4,9,0]. we have these transactions (4-1=3)(7-2=5)(9-2=7) and max profit should be 5+7=12. But the actual max should be (7-1) + (9-2) = 13.
Then try the DP solution. Suppose we have four state, buy1, buy2, sell1 and sell2.
Then we can know that the change of state is buy1 to sell1 to buy2 to sell2. And let’s make the initial money to 0, if we buy a stock at price i, we have 0-i. And sell at j, we have 0-i+j as profit.
So we have:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int maxProfit(int[] prices) {
int s1 = 0, s2 = 0, b1 = Integer.MIN_VALUE, b2 = Integer.MIN_VALUE;
for (int i:prices){
b1 = Math.max(b1, -i);
s1 = Math.max(b1+i, s1);
b2 = Math.max(s1-i, b2);
s2 = Math.max(b2+i, s2);
}
return Math.max(s1,s2);
}
}
What to improve
- to make sure buy at the first price, the initial value of buy should be MIN_VALUE