123 Best Time to Buy and Sell Stock III – Hard¶
Problem:¶
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 (ie, you must sell the stock before you buy again).
Thoughts:¶
We will need to divide this problem into two subproblem. We find the max profit for range 0..i and i + 1..n -1, then we add up the two max profit we will get the expected result.
Solutions:¶
public class Solution {
public int maxProfit(int[] prices) {
int[] first = new int[prices.length];
//first[i] is the max profit for the range 0 .. i,
int minPrice = Integer.MAX_VALUE;
int max = 0;
for (int i = 0; i < prices.length; i ++) {
minPrice = Math.min(minPrice, prices[i]);
max = Math.max(max, prices[i] - minPrice);
first[i] = max;
}
int maxPrice = Integer.MIN_VALUE;
max = 0;
for (int i = prices.length - 1; i > 0; i --) {
maxPrice = Math.max(maxPrice, prices[i]);
max = Math.max(max, maxPrice - prices[i] + first[i-1]);
}
if (prices.length > 0) {
max = Math.max(max, first[first.length - 1]);
}
return max;
}
}
class Solution {
public int maxProfit(int[] prices) {
int[][][] dp = new int[prices.length+1][3][2];
int res = 0;
dp[0][0][0] = dp[0][1][0] = dp[0][2][0] = 0 ;
dp[0][0][1] = dp[0][1][1] = dp[0][2][1] = Integer.MIN_VALUE;
for (int i = 1; i <= prices.length; i ++) {
dp[i][0][0] = 0;
dp[i][0][1] = Integer.MIN_VALUE;
dp[i][1][0] = Math.max(dp[i-1][1][0], dp[i-1][1][1] + prices[i-1]);
dp[i][1][1] = Math.max(dp[i-1][1][1], dp[i-1][0][0] - prices[i-1]);
dp[i][2][0] = Math.max(dp[i-1][2][0], dp[i-1][2][1] + prices[i-1]);
dp[i][2][1] = Math.max(dp[i-1][2][1], dp[i-1][1][0] - prices[i-1]);
System.out.println(dp[i][1][0] +", " + dp[i][1][1] + ", " + dp[i][2][0] + ", " + dp[i][2][1]);
for (int j = 0; j < 3; j ++) {
for (int k = 0; k < 2; k ++) {
res = Math.max(res, dp[i][j][k]);
}
}
}
return res;
}
}