Skip to content

Commit f4077ed

Browse files
fishercoder1534fishercoder1534
committed
best time to buy and sell stock III
1 parent 870e028 commit f4077ed

File tree

1 file changed

+130
-0
lines changed

1 file changed

+130
-0
lines changed

‎HARD/src/hard/BestTimeToBuyAndSellStockIII.java

+130
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,130 @@
1+
package hard;
2+
3+
4+
/**123. Best Time to Buy and Sell Stock III QuestionEditorial Solution My Submissions
5+
Total Accepted: 62880
6+
Total Submissions: 231914
7+
Difficulty: Hard
8+
Say you have an array for which the ith element is the price of a given stock on day i.
9+
10+
Design an algorithm to find the maximum profit. You may complete at most two transactions.
11+
12+
Note:
13+
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).*/
14+
public class BestTimeToBuyAndSellStockIII {
15+
16+
//this is a very clear solution and very highly upvoted in Discuss, but not extensibel to K solution.
17+
public int maxProfit(int[] prices) {
18+
if(prices.length < 2) return 0;
19+
int buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;//we use negative numbers to denote buy1 and buy2, thus use Integer.MIN_VALUE here is more convenient.
20+
int sell1 = 0, sell2 = 0;
21+
for(int i = 0; i < prices.length; i++){
22+
buy1 = Math.max(buy1, -prices[i]);
23+
sell1 = Math.max(sell1, buy1+prices[i]);
24+
buy2 = Math.max(buy2, sell1-prices[i]);
25+
sell2 = Math.max(sell2, buy2+prices[i]);
26+
}
27+
return sell2;
28+
}
29+
30+
//this one could make it AC'ed on OJ, but when I use this one to BestTimeToBuyAndSellStockIV, it got Memory Limit Exceeded.
31+
//this one is optimized from maxProfit_optimized() below
32+
public int maxProfit_optimized(int[] prices) {
33+
if(prices.length < 2) return 0;
34+
int K = 2;
35+
int[][] dp = new int[K+1][prices.length];
36+
for(int i = 1; i <= K; i++){
37+
int maxDiff = -prices[0];
38+
for(int j = 1; j < prices.length; j++){
39+
dp[i][j] = Math.max(dp[i][j-1], prices[j] + maxDiff);
40+
maxDiff = Math.max(maxDiff, dp[i-1][j] - prices[j]);
41+
}
42+
}
43+
return dp[K][prices.length-1];
44+
}
45+
46+
//
47+
public int maxProfit_TLE(int[] prices) {
48+
/**
49+
* Thanks to this post: https://discuss.leetcode.com/topic/4766/a-clean-dp-solution-which-generalizes-to-k-transactions/29
50+
* and Tushar's video:https://www.youtube.com/watch?v=oDhu5uGq_ic&feature=youtu.be
51+
*
52+
* use this dp strategy:
53+
*
54+
* dp[i][j] = Math.max(dp[i][j-1], (prices[i] - prices[m]) + dp[i-1][m]) with m in (0, j-1)
55+
* row is price
56+
* column is day
57+
* dp[i][j] means the max profit you can make on day j by doing a max of i transactions.
58+
*
59+
* dp[i][j-1]
60+
* means no transaction on day j, so the max profit you could get is on the previous day j-1
61+
*
62+
* (prices[i] - prices[m]) + dp[i-1][m]
63+
* (prices[i] - prices[m]) means you'll sell on day j, this means you'll do one transaction on day j with sell price: prices[m],
64+
* and the buy price could be any price that is on the day prior to day j, we call it day m, thus m is
65+
* in this range: (0, j-1)
66+
* dp[i-1][m] means you'll have i-1 transaction to do on day m to make up to i transactions, since you do one transaction on day j, that's why
67+
* we deduct 1 from i
68+
*
69+
* */
70+
if(prices.length < 2) return 0;
71+
else {
72+
/**First row should be zero because it means, you're allowed to make ZERO transaction, so no profit
73+
* First column should be zero because it means, on day ZERO, you could only buy and make no profit*/
74+
int K = 2;//number of allowed transactions.
75+
int dp[][] = new int[K+1][prices.length];
76+
for(int i = 1; i <= K; i++){
77+
for(int j = 1; j < prices.length; j++){
78+
int maxProfitOnDayJ = 0;
79+
for(int m = 0; m < j; m++){
80+
maxProfitOnDayJ = Math.max(maxProfitOnDayJ, prices[j] - prices[m] + dp[i-1][m]);
81+
}
82+
dp[i][j] = Math.max(dp[i][j-1], maxProfitOnDayJ);
83+
}
84+
}
85+
return dp[K][prices.length-1];
86+
}
87+
}
88+
89+
public static void main(String...strings){
90+
// int[] prices = new int[]{6,1,3,2,4,7};
91+
// int[] prices = new int[]{1,2,4,2,5,7,2,4,9,0};//(7-2)+(9-2) = 5+7 = 12 is wrong, it should be (7-1)+(9-2) = 6+7 = 13
92+
int[] prices = new int[]{2,5,7,1,4,3,1,3};
93+
BestTimeToBuyAndSellStockIII test = new BestTimeToBuyAndSellStockIII();
94+
System.out.println(test.maxProfit(prices));
95+
}
96+
97+
/**I try to find the regional max price, then compute the profit, but failed at this test case:
98+
* 1,2,4,2,5,7,2,4,9,0*/
99+
public int maxProfit_2nd_attempt(int[] prices) {
100+
int[] profits = new int[2];
101+
boolean flip = false;
102+
for(int i = 1; i < prices.length; i++){
103+
int buyPrice = prices[i-1];
104+
if(prices[i] > prices[i-1]) flip = true;
105+
while(i < prices.length && prices[i] > prices[i-1]) i++;
106+
if(flip) i--;
107+
int profit = prices[i] - buyPrice;
108+
//update the smaller profit in profits array
109+
int smallerIndex = profits[0] < profits[1] ? 0 : 1;
110+
profits[smallerIndex] = Math.max(profits[smallerIndex], profit);
111+
flip = false;;
112+
}
113+
return profits[0] + profits[1];
114+
}
115+
116+
/**Greedy approach won't work like Best Time to Buy and Sell Stock II because:
117+
* 1. we need to track a regional min buy price instead of just the previous one;
118+
* 2. we're allowed to do only TWO transactions.
119+
* e.g test case: 6,1,3,2,4,7*/
120+
public int maxProfit_1st_attempt(int[] prices) {
121+
int[] profits = new int[2];
122+
for(int i = 1; i < prices.length; i++){
123+
if(prices[i] > prices[i-1]){
124+
int smallerIndex = profits[0] > profits[1] ? 1 : 0;
125+
profits[smallerIndex] = Math.max(prices[i] - prices[i-1], profits[smallerIndex]);
126+
}
127+
}
128+
return profits[0] + profits[1];
129+
}
130+
}

0 commit comments

Comments
 (0)