Skip to content

Commit dadf541

Browse files
fishercoder1534fishercoder1534
committed
refactor 309
1 parent fa6cca9 commit dadf541

File tree

1 file changed

+57
-53
lines changed
  • src/main/java/com/fishercoder/solutions

1 file changed

+57
-53
lines changed

‎src/main/java/com/fishercoder/solutions/_309.java

Lines changed: 57 additions & 53 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,9 @@
11
package com.fishercoder.solutions;
22

3-
/**Say you have an array for which the ith element is the price of a given stock on day i.
3+
/**
4+
* 309. Best Time to Buy and Sell Stock with Cooldown
5+
*
6+
* Say you have an array for which the ith element is the price of a given stock on day i.
47
58
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
69
@@ -10,54 +13,55 @@ You may not engage in multiple transactions at the same time (ie, you must sell
1013
1114
prices = [1, 2, 3, 0, 2]
1215
maxProfit = 3
13-
transactions = [buy, sell, cooldown, buy, sell]*/
16+
transactions = [buy, sell, cooldown, buy, sell]
17+
*/
1418
public class _309 {
15-
static class solutionFromProblemAuthor {
19+
public static class Solution1 {
1620
/**
1721
* The series of problems are typical dp. The key for dp is to find the variables to
1822
* represent the states and deduce the transition function.
19-
*
23+
*
2024
* Of course one may come up with a O(1) space solution directly, but I think it is better
2125
* to be generous when you think and be greedy when you implement.
22-
*
26+
*
2327
* The natural states for this problem is the 3 possible transactions : buy, sell, rest.
2428
* Here rest means no transaction on that day (aka cooldown).
25-
*
29+
*
2630
* Then the transaction sequences can end with any of these three states.
27-
*
31+
*
2832
* For each of them we make an array, buy[n], sell[n] and rest[n].
29-
*
33+
*
3034
* buy[i] means before day i what is the maxProfit for any sequence end with buy.
31-
*
35+
*
3236
* sell[i] means before day i what is the maxProfit for any sequence end with sell.
33-
*
37+
*
3438
* rest[i] means before day i what is the maxProfit for any sequence end with rest.
35-
*
39+
*
3640
* Then we want to deduce the transition functions for buy sell and rest. By definition we
3741
* have:
38-
*
42+
*
3943
* buy[i] = max(rest[i-1]-price, buy[i-1])
40-
* sell[i] = max(buy[i-1]+price, sell[i-1])
41-
* rest[i] = max(sell[i-1], buy[i-1], rest[i-1])
42-
*
44+
* sell[i] = max(buy[i-1]+price, sell[i-1])
45+
* rest[i] = max(sell[i-1], buy[i-1], rest[i-1])
46+
*
4347
* Where price is the price of day i. All of these are very straightforward. They simply represents :
44-
*
45-
* (1) We have to `rest` before we `buy` and
46-
* (2) we have to `buy` before we `sell`
48+
*
49+
* (1) We have to `rest` before we `buy` and
50+
* (2) we have to `buy` before we `sell`
4751
* One tricky point is how do you make sure you sell before you buy, since from the equations it seems that [buy, rest, buy] is entirely possible.
48-
*
52+
*
4953
* Well, the answer lies within the fact that buy[i] <= rest[i] which means rest[i] =
5054
* max(sell[i-1], rest[i-1]). That made sure [buy, rest, buy] is never occurred.
51-
*
55+
*
5256
* A further observation is that and rest[i] <= sell[i] is also true therefore
53-
*
57+
*
5458
* rest[i] = sell[i-1] Substitute this in to buy[i] we now have 2 functions instead of 3:
55-
*
59+
*
5660
* buy[i] = max(sell[i-2]-price, buy[i-1]) sell[i] = max(buy[i-1]+price, sell[i-1]) This is
5761
* better than 3, but
58-
*
62+
*
5963
* we can do even better
60-
*
64+
*
6165
* Since states of day i relies only on i-1 and i-2 we can reduce the O(n) space to O(1).
6266
* And here we are at our final solution:
6367
*/
@@ -75,49 +79,49 @@ public int maxProfit(int[] prices) {
7579
return sell;
7680
}
7781
}
78-
79-
static class solutionWithTheSecondHighestUpvotes {
82+
83+
public static class Solution2 {
8084
/**Surprisingly, this solution is even much faster than the one above provided by the author.*/
8185
/**
8286
* Here I share my no brainer weapon when it comes to this kind of problems.
83-
*
87+
*
8488
* 1. Define States
85-
*
89+
*
8690
* To represent the decision at index i:
87-
*
88-
* buy[i]: Max profit till index i. The series of transaction is ending with a buy.
89-
* sell[i]: Max profit till index i. The series of transaction is ending with a sell.
90-
*
91+
*
92+
* buy[i]: Max profit till index i. The series of transaction is ending with a buy.
93+
* sell[i]: Max profit till index i. The series of transaction is ending with a sell.
94+
*
9195
* 2. Define Recursion
92-
*
96+
*
9397
* buy[i]: To make a decision whether to buy at i, we either take a rest, by just using the
9498
* old decision at i - 1, or sell at/before i - 2, then buy at i, We cannot sell at i - 1,
95-
* then buy at i, because of cooldown.
96-
* sell[i]: To make a decision whether to sell at i, we either take a rest, by just using the old decision at i - 1,
97-
* or buy at/before i - 1, then sell at i.
98-
*
99+
* then buy at i, because of cooldown.
100+
* sell[i]: To make a decision whether to sell at i, we either take a rest, by just using the old decision at i - 1,
101+
* or buy at/before i - 1, then sell at i.
102+
*
99103
* So we get the following formula:
100-
*
101-
* buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
102-
* sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
103-
*
104+
*
105+
* buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
106+
* sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
107+
*
104108
* 3. Optimize to O(1) Space
105-
*
109+
*
106110
* DP solution only depending on i - 1 and i - 2 can be optimized using O(1) space.
107-
*
108-
* Let b2, b1, b0 represent buy[i - 2], buy[i - 1], buy[i]
109-
* Let s2, s1, s0 represent sell[i - 2], sell[i - 1], sell[i]
110-
*
111+
*
112+
* Let b2, b1, b0 represent buy[i - 2], buy[i - 1], buy[i]
113+
* Let s2, s1, s0 represent sell[i - 2], sell[i - 1], sell[i]
114+
*
111115
* Then arrays turn into Fibonacci like recursion:
112-
*
113-
* b0 = Math.max(b1, s2 - prices[i]);
114-
* s0 = Math.max(s1, b1 + prices[i]);
115-
*
116+
*
117+
* b0 = Math.max(b1, s2 - prices[i]);
118+
* s0 = Math.max(s1, b1 + prices[i]);
119+
*
116120
* 4. Write Code in 5 Minutes
117-
*
121+
*
118122
* First we define the initial states at i = 0:
119-
*
120-
* We can buy. The max profit at i = 0 ending with a buy is -prices[0].
123+
*
124+
* We can buy. The max profit at i = 0 ending with a buy is -prices[0].
121125
* We cannot sell. The max profit at i = 0 ending with a sell is 0.
122126
*/
123127
public int maxProfit(int[] prices) {

0 commit comments

Comments
 (0)