The trick here is to name the state correctly, then let the implementation follow. For 122. Best Time to Buy and Sell Stock II, the solution in this repository is mainly a greedy solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: greedy.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are maxProfit, calculate.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02Say you have an array for which the ith element is the price of a given stock on day i.
03
04Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
05
06Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
07
08Example 1:
09
10Input: [7,1,5,3,6,4]
11Output: 7
12Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
13 Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
14Example 2:
15
16Input: [1,2,3,4,5]
17Output: 4
18Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
19 Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
20 engaging multiple transactions at the same time. You must sell before buying again.
21Example 3:
22
23Input: [7,6,4,3,1]
24Output: 0
25Explanation: In this case, no transaction is done, i.e. max profit = 0.
26**/
27
28//Runtime: 8 ms, faster than 99.42% of C++ online submissions for Best Time to Buy and Sell Stock II.
29//Memory Usage: 9.3 MB, less than 97.55% of C++ online submissions for Best Time to Buy and Sell Stock II.
30class Solution {
31public:
32 int maxProfit(vector<int>& prices) {
33 if(prices.size() == 0) return 0;
34
35 int ans = 0;
36 int start = prices[0], end = prices[0];
37
38 for(int i = 0; i < prices.size(); i++){
39 if(prices[i] > end){
40 //still in the old session
41 //update old end
42 end = prices[i];
43 }else{
44 //sell
45 ans += (end - start);
46 //restart a session
47 start = prices[i];
48 end = prices[i];
49 }
50 }
51
52 if(end > start) ans += (end - start);
53
54 return ans;
55 }
56};
57
58
59/**
60Solution
61Approach 1: Brute Force
62In this case, we simply calculate the profit corresponding to all the possible sets of transactions and find out the maximum profit out of them.
63**/
64
65/**
66//Java
67class Solution {
68 public int maxProfit(int[] prices) {
69 return calculate(prices, 0);
70 }
71
72 public int calculate(int prices[], int s) {
73 if (s >= prices.length)
74 return 0;
75 int max = 0;
76 for (int start = s; start < prices.length; start++) {
77 int maxprofit = 0;
78 for (int i = start + 1; i < prices.length; i++) {
79 if (prices[start] < prices[i]) {
80 int profit = calculate(prices, i + 1) + prices[i] - prices[start];
81 if (profit > maxprofit)
82 maxprofit = profit;
83 }
84 }
85 if (maxprofit > max)
86 max = maxprofit;
87 }
88 return max;
89 }
90}
91**/
92
93/**
94Complexity Analysis
95
96Time complexity : O(n^n). Recursive function is called n^n times.
97
98Space complexity : O(n). Depth of recursion is nn.
99**/
100
101/**
102Approach 2: Peak Valley Approach
103Algorithm
104
105Say the given array is:
106
107[7, 1, 5, 3, 6, 4].
108
109If we plot the numbers of the given array on a graph, we get:
110**/
111
112/**
113If we analyze the graph, we notice that the points of interest are the consecutive valleys and peaks.
114
115Mathematically speaking: Total Profit= \sum_{i}(height(peak_i)-height(valley_i)) TotalProfit=∑ i(height(peak i)−height(valley i))
116
117The key point is we need to consider every peak immediately following a valley to maximize the profit. In case we skip one of the peaks (trying to obtain more profit), we will end up losing the profit over one of the transactions leading to an overall lesser profit.
118
119For example, in the above case, if we skip peak_ipeak i and valley_jvalley j trying to obtain more profit by considering points with more difference in heights, the net profit obtained will always be lesser than the one obtained by including them, since CC will always be lesser than A+BA+B.
120**/
121
122/**
123Complexity Analysis
124Time complexity : O(n). Single pass.
125Space complexity : O(1). Constant space required.
126**/
127
128class Solution {
129public:
130 int maxProfit(vector<int>& prices) {
131 if(prices.size() == 0) return 0;
132 int ans = 0;
133 int valley = prices[0], peak = prices[0];
134 int cur = 0;
135
136 while(cur < prices.size() - 1){
137 //find valley, it's smaller than its right point
138 while(cur < prices.size() - 1 && prices[cur] >= prices[cur+1]){
139 cur++;
140 }
141 valley = prices[cur];
142
143 //find peak, it's larger than its right point
144 while(cur < prices.size() - 1 && prices[cur] <= prices[cur+1]){
145 cur++;
146 }
147 peak = prices[cur];
148 ans += (peak - valley);
149 }
150 return ans;
151 }
152};
153
154/**
155Approach 3: Simple One Pass
156Algorithm
157
158This solution follows the logic used in Approach 2 itself, but with only a slight variation. In this case, instead of looking for every peak following a valley, we can simply go on crawling over the slope and keep on adding the profit obtained from every consecutive transaction. In the end,we will be using the peaks and valleys effectively, but we need not track the costs corresponding to the peaks and valleys along with the maximum profit, but we can directly keep on adding the difference between the consecutive numbers of the array if the second number is larger than the first one, and at the total sum we obtain will be the maximum profit. This approach will simplify the solution. This can be made clearer by taking this example:
159
160[1, 7, 2, 3, 6, 7, 6, 7]
161
162The graph corresponding to this array is:
163**/
164
165/**
166From the above graph, we can observe that the sum A+B+CA+B+C is equal to the difference DD corresponding to the difference between the heights of the consecutive peak and valley.
167**/
168
169/**
170Complexity Analysis
171
172Time complexity : O(n)O(n). Single pass.
173
174Space complexity: O(1)O(1). Constant space needed.
175**/
176
177class Solution {
178public:
179 int maxProfit(vector<int>& prices) {
180 if(prices.size() == 0) return 0;
181 int ans = 0;
182 for(int i = 0; i < prices.size() - 1; i++){
183 ans += max(0, prices[i+1] - prices[i]);
184 }
185 return ans;
186 }
187};
188
189//Greedy
190//Runtime: 12 ms, faster than 15.03% of C++ online submissions for Best Time to Buy and Sell Stock II.
191//Memory Usage: 13.4 MB, less than 6.35% of C++ online submissions for Best Time to Buy and Sell Stock II.
192class Solution {
193public:
194 int maxProfit(vector<int>& prices) {
195 int lastMin = INT_MAX;
196 int ans = 0;
197
198 for(int price : prices){
199 if(price - lastMin > 0){
200 ans += (price - lastMin);
201 //lastMin is used, so update it
202 lastMin = price;
203 }else{
204 //continue to find the minimum
205 lastMin = min(lastMin, price);
206 }
207 }
208
209 return ans;
210 }
211};
212
213//monotonic deque
214//Runtime: 12 ms, faster than 71.71% of C++ online submissions for Best Time to Buy and Sell Stock II.
215//Memory Usage: 13.5 MB, less than 5.41% of C++ online submissions for Best Time to Buy and Sell Stock II.
216//time: O(N), space: O(N)
217class Solution {
218public:
219 int maxProfit(vector<int>& prices) {
220 int n = prices.size();
221
222 //just for trigger when the scanning ends
223 prices.push_back(0);
224 //increasing deque
225 deque<int> deq;
226
227 int profit = 0;
228
229 for(int i = 0; i < n+1; ++i){
230 /*
231 start to process deque's content
232 when we meet a smaller element
233 */
234 /*
235 we will process all elements from deque in one pass,
236 so don't need a while loop here
237 */
238 if(!deq.empty() && prices[i] < prices[deq.back()]){
239 /*
240 only when there are >= 2 choosable prices,
241 we can start a transaction
242 */
243 if(deq.size() >= 2){
244 profit += prices[deq.back()] - prices[deq.front()];
245 }
246 deq.clear();
247 }
248
249 deq.push_back(i);
250 }
251
252 return profit;
253 }
254};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.