Let's make this one less mysterious. For 188. Best Time to Buy and Sell Stock IV, the solution in this repository is mainly a dynamic programming 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: dynamic programming.
The notes already sitting in the source point us in the right direction:
- 209 / 211 test cases passed.
- time: O(N*k), space: O(k)
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are maxProfit, holds, cashs.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- 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:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
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*k), space: O(min(n,k))
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime error(MLE)
02//209 / 211 test cases passed.
03//time: O(N*k), space: O(k)
04class Solution {
05public:
06 int maxProfit(int k, vector<int>& prices) {
07 int n = prices.size();
08 //0th element for padding
09 vector<int> holds(k+1, INT_MIN);
10 vector<int> cashs(k+1, 0);
11 int ans = 0;
12
13 for(int price : prices){
14 // cout << "price: " << price << endl;
15 for(int i = k; i >= 1; i--){
16 /*
17 we should update cashs[i] and then holds[i]!
18 because when we update cashs[i],
19 we need holds[i] in last iteration!
20 */
21 /*
22 hold-cash makes a transaction,
23 so holds[i]+price means
24 selling the stock bought in ith transaction
25 */
26 cashs[i] = max(cashs[i], holds[i]+price);
27 holds[i] = max(holds[i], cashs[i-1]-price);
28 // cout << i << ", " << holds[i] << ", " << cashs[i] << endl;
29 ans = max(ans, cashs[i]);
30 }
31 }
32
33 return ans;
34 }
35};
36
37//Time Limit Exceeded
38//209 / 211 test cases passed.
39//time: O(N*k), space: O(min(n,k))
40class Solution {
41public:
42 int maxProfit(int k, vector<int>& prices) {
43 int n = prices.size();
44 //0th element for padding
45 vector<int> holds(min(n,k)+1, INT_MIN);
46 vector<int> cashs(min(n,k)+1, 0);
47 int ans = 0;
48
49 for(int price : prices){
50 // cout << "price: " << price << endl;
51 for(int i = min(n,k); i >= 1; i--){
52 /*
53 we should update cashs[i] and then holds[i]!
54 because when we update cashs[i],
55 we need holds[i] in last iteration!
56 */
57 /*
58 hold-cash makes a transaction,
59 so holds[i]+price means
60 selling the stock bought in ith transaction
61 */
62 cashs[i] = max(cashs[i], holds[i]+price);
63 holds[i] = max(holds[i], cashs[i-1]-price);
64 // cout << i << ", " << holds[i] << ", " << cashs[i] << endl;
65 ans = max(ans, cashs[i]);
66 }
67 }
68
69 return ans;
70 }
71};
72
73//add quick solution for larger enough k
74//https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/discuss/54113/A-Concise-DP-Solution-in-Java
75//Runtime: 8 ms, faster than 71.12% of C++ online submissions for Best Time to Buy and Sell Stock IV.
76//Memory Usage: 12.1 MB, less than 5.55% of C++ online submissions for Best Time to Buy and Sell Stock IV.
77class Solution {
78public:
79 int maxProfit(int k, vector<int>& prices) {
80 int n = prices.size();
81 int ans = 0;
82
83 //we can do as many transactions as we want
84 if(k >= n/2){
85 for(int i = 1; i < n; i++){
86 ans += max(0, prices[i]-prices[i-1]);
87 }
88 return ans;
89 }
90
91 //0th element for padding
92 vector<int> holds(min(n,k)+1, INT_MIN);
93 vector<int> cashs(min(n,k)+1, 0);
94
95 for(int price : prices){
96 // cout << "price: " << price << endl;
97 for(int i = min(n,k); i >= 1; i--){
98 /*
99 we should update cashs[i] and then holds[i]!
100 because when we update cashs[i],
101 we need holds[i] in last iteration!
102 */
103 /*
104 hold-cash makes a transaction,
105 so holds[i]+price means
106 selling the stock bought in ith transaction
107 */
108 cashs[i] = max(cashs[i], holds[i]+price);
109 holds[i] = max(holds[i], cashs[i-1]-price);
110 // cout << i << ", " << holds[i] << ", " << cashs[i] << endl;
111 ans = max(ans, cashs[i]);
112 }
113 }
114
115 return ans;
116 }
117};
118
119//DP
120//https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/discuss/54117/Clean-Java-DP-solution-with-comment
121//Runtime: 8 ms, faster than 71.12% of C++ online submissions for Best Time to Buy and Sell Stock IV.
122//Memory Usage: 13 MB, less than 5.55% of C++ online submissions for Best Time to Buy and Sell Stock IV.
123class Solution {
124public:
125 int maxProfit(int k, vector<int>& prices) {
126 int n = prices.size();
127 int ans = 0;
128
129 if(k >= n/2){
130 for(int i = 1; i < n; i++){
131 ans += max(0, prices[i]-prices[i-1]);
132 }
133 return ans;
134 }
135
136 /**
137 * dp[i, j] represents the max profit up until prices[j] using at most i transactions.
138 * dp[i, j] = max(dp[i, j-1], prices[j] - prices[jj] + dp[i-1, jj]) { jj in range of [0, j-1] }
139 * = max(dp[i, j-1], prices[j] + max(dp[i-1, jj] - prices[jj]))
140 * dp[0, j] = 0; 0 transactions makes 0 profit
141 * dp[i, 0] = 0; if there is only one price data point you can't make any transaction.
142 */
143 //only pad for k(transactions) dimension, not time dimension
144 vector<vector<int>> dp(k+1, vector(n, 0));
145 for(int i = 1; i <= k; i++){ //transactions
146 // int hold = INT_MIN; //this gives WA!!
147 int hold = dp[i-1][0] - prices[0];
148 for(int j = 1; j < n; j++){ //days
149 //hold: the max money we have if we hold a stock until j-1 day
150 dp[i][j] = max(dp[i][j-1], prices[j] + hold);
151 hold = max(hold, dp[i-1][j] - prices[j]);
152 }
153 }
154
155 return dp[k][n-1];
156 }
157};Cost
Complexity
Time
O(N*k), space: O(min(n,k))
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.