Repository navigation
Expand file tree
/
Copy pathBest Time to Buy and Sell Stock II.java
More file actions
executable file
·224 lines (195 loc) · 7.69 KB
/
Copy pathBest Time to Buy and Sell Stock II.java
File metadata and controls
executable file
·224 lines (195 loc) · 7.69 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
E
1531717353
tags: Array, Greedy, DP, Sequence DP, Status DP
time: O(n)
space: O(1) greedy, O(n) dp
和Stock I 的区别：可以买卖多次，求总和的最大盈利.
#### 几种其他不同的思路:
- Greedy, 每次有相邻的diff符合profit条件, 就卖了, 最后把所有的diff加在一起. 计算delta, 其实简单粗暴, 也还不错.
- 如下, 从低谷找peek, sell.
- DP. (old dp solution BuyOn[], SellOn[])
- DFS计算所有(timeout).Improvement on DFS -> DP -> calculate sellOn[i] and buyOn[i], and then return buyOn[i]. 有点难想, 但是代码简单, 也是O(n)
#### Greedy
- 画图, 因为可以无限买卖, 所以只要有上升, 就有profit
- 所有卖掉的, 平移加起来, 其实就是overall best profit
- O(n)
#### 找涨幅最大的区间，买卖：
- 找到低谷，买进:peek = start + 1 时候，就是每次往前走一步;若没有上涨趋势，继续往低谷前进。
- 涨到峰顶，卖出:一旦有上涨趋势，进一个while loop，涨到底, 再加个profit.
- profit += prices[peek - 1] - prices[start]; 挺特别的。
- 当没有上涨趋势时候，peek-1也就是start, 所以这里刚好profit += 0.
#### DP, sequence dp + status
- 想知道前i天的最大profit, 那么用sequence DP:
- dp[i]: represents 前i天的最大profit
- 当天的是否能卖, 取决于昨天是否买进, 也就是 `昨天买了或者卖了的状态`: 加状态, dp[i][0], dp[i][1]
- `买`的状态 `dp[i][0]` = 1. 今天买入, 昨天卖掉的dp[i-1][1]结果 - price[i]; 2. 今天不买, 跟昨天买的status dp[i-1][0] 结果 比较.
- `卖`的状态 `dp[i][1]` = 1. 今天卖出, 昨天买进的dp[i-1][0]结果 + price[i]; 2. 今天不卖, 跟昨天卖的status dp[i-1][1] 结果 比较.
- 注意init:
- dp[0][0] = dp[0][1] = 0; // 0 days,
- dp[1][0] = 0; // sell on 1st day, haven't bought, so just 0 profit.
- dp[1][0] = -prices[0]; // buy on 1st day, with cost of prices[0]
##### Rolling Array
- [i] 和 [i - 1] 相关联, roll
```
/*
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 as many transactions as you like
(ie, buy one and sell one share of the stock multiple times).
However, you may not engage in multiple transactions
at the same time (ie, you must sell the stock before you buy again).
Example
Given an example [2,1,2,0,1], return 2
Tags Expand
Greedy Enumeration Array
*/
/*
Thoughts:
Draw a curve and realize that, only when prices[i] > prices[i - 1],
we complete buy/sell and take the profit.
Adding more slopes can be greater than 0~N overall height diff.
// Greedy
*/
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
}
//DP: See details at notes above
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int n = prices.length;
int[][] dp = new int[n + 1][2];
dp[0][0] = dp[0][1] = 0;
dp[1][1] = 0;
dp[1][0] = - prices[0];// -2
for (int i = 2; i <= n; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i - 1]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i - 1]);
}
return dp[n][1]; //return Math.max(dp[n][1], dp[n][0]);
}
};
// Rolling array
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int n = prices.length;
int[][] dp = new int[2][2];
dp[0][0] = dp[0][1] = 0;
dp[1][0] = - prices[0];
for (int i = 2; i <= n; i++) {
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) % 2][0] + prices[i - 1]);
}
return dp[n % 2][1];
}
};
/*
Previous notes about the above solution:
Greedy: when seeing a increase, sell, accumulate the delta benefits.
For instance, at a inclining slope, the sum of delta changes between (i-1, i) equals to the increase of (0 , n), so it's okay to do greedy.
But this is less inteligent, and not very applicable
*/
/*
Thought:
In this case, since we know the entire stock price for all days in the array, we want to this:
Sell it at nearest peek price and buy it on the next dropped price, then sell again at next peek.
Two pointers, start and peek, to track the starting point and the peek.
Two while loop:
While loop on start, until start reaches the last 2nd index, we only have 1 option to sell.
Inner while loop that finds the peek from start.
Note: peek always has index >= start+1.
Sum up all profit and return it.
Tricky thing: we are looking for max profit, but does not require to sell the stock by end of array.
So if the price is dropping, we are not selling and we are not losing/winning anything.
*/
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}
int curr = 0;
int profit = 0;
int peek = 1;
while(curr < prices.length) {
while (peek < prices.length && prices[peek - 1] <= prices[peek]) {
peek++;
}
profit += prices[peek - 1] - prices[curr];
curr = peek;
peek = curr + 1;
}
return profit;
}
}
/*
Thoughts:
Optimize the DFS (since it times out)
buyOn[i]: [i ~ n], if buying on day i, what's the best profit
sellOn[i]: [i ~ n], if selling on day i, what's the best profit.
equation:
buyOn[i]: on day i, we can buy && sell on day [i + 1], or do nothing.
sellOn[i]: on day i, we can sell && buy on day [i + 1], or do nothing.
buyOn[0]: max value will be calculated and saved up here.
O(n)
However, still very slow, only beat 2%
*/
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}
int[] buyOn = new int[prices.length];
int[] sellOn = new int[prices.length];
int length = prices.length;
buyOn[length - 1] = 0;
sellOn[length - 1] = prices[length - 1];
for (int i = length - 2; i >= 0; i--) {
buyOn[i] = Math.max(buyOn[i + 1], sellOn[i + 1] - prices[i]); // (not buying on day i; buying on day i, so - prices[i])
sellOn[i] = Math.max(sellOn[i + 1], buyOn[i + 1] + prices[i]);// (not selling on day i; selling on day i, so + prices[i])
}
return Math.max(0, buyOn[0]);
}
}
/*
Thoughts:
On given day: we can choose to buy or sell or move with no action, which generates different paths -> DFS
However: 196 / 198 test cases passed but times out.
*/
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}
return Math.max(dfs(prices, 1, true) - prices[0], dfs(prices, 1, false));
}
private int dfs(int[] prices, int index, boolean sellStatus) {
if (index == prices.length - 1) {
return sellStatus ? prices[index] : 0;
}
int profit = 0;
for (int i = index; i < prices.length; i++) {
//No action
profit = Math.max(profit, dfs(prices, i + 1, sellStatus));
//Sell or buy:
int levelDelta = sellStatus ? prices[i] : - prices[i];
profit = Math.max(profit, dfs(prices, i + 1, !sellStatus) + levelDelta);
}
return profit;
}
}
```