# Share my C++ DP solution with O(kn) time O(k) space, 10ms

• This is my DP solution:

class Solution {

``````public:
int maxProfit(int k, vector<int> &prices) {
int len = prices.size();
if (len<2) return 0;
if (k>len/2){ // simple case
int ans = 0;
for (int i=1; i<len; ++i){
ans += max(prices[i] - prices[i-1],0);
}
return ans;
}
int hold[k+1];
int rele[k+1];
for (int i=0;i<=k;++i){
hold[i] = INT_MIN;
rele[i] = 0;
}
int cur;
for (int i=0; i<len; ++i){
cur = prices[i];
for(int j=k; j>0; --j){
rele[j] = max(rele[j],hold[j] + cur);
hold[j] = max(hold[j],rele[j-1] - cur);
}
}
return rele[k];
}
``````

};

Inspired by weijiac in Best Time to Buy and Sell Stock III

https://leetcode.com/discuss/18330/is-it-best-solution-with-o-n-o-1

• I tried a similar solution in java but it fails to allocate heap space for one of the test cases where k = 1,000,000,000

• I met too.
Finally I found that k should never be bigger than length of prices.
In that case, the length is only 1000.

• test cases with k larger than prices.size()/2 would fail (don't know reason), you need to rule it out by using the method of buying stock with any number of transactions

• I think if k is large you need to DP over the length of prices than the length of k.

• Well, I think the transaction times should be <= half of the number of days(i.e. the prices). Since we need two days to finish a transaction~

• I use a `vector<int>` instead of your `int hold[k+1]` then I got a TLE...
Maybe they just don't turn on the O2 optimization...
After look at your code, I revised mine and got Accepted.

• I think the answer was edited after your posts, but anyhow I tried it in Java and works fine.

• shouldn't the trial case be k >= n - 1 instead of n/2?
For n days there are at most n - 1 transactions you can make.

• Acturally, do not need to let k>=n-1. If you do n-1 transactions in n days, then the prices must be non-decreasing. For n days, we do at most n/2 transactions, when the size of longest increasing sequenen is just 2. That is 1 3 1 2 1 4... , something like this. If there is an increasing sequenen which is longer than 2, we just need once transaction. Have I explained this clearly?

• I slightly change your solution to make it better understand.
At each buy, instead of `max(hold[j],rele[j-1] - cur)`, we actually want a lower buy price which gives: `min(hold[j], prices[i]-rele[j-1])` Also, at each sell, the profit should be: `max(rele[j], prices[i]-hold[j])`

``````class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int maxProfit=0;

if(prices.size()<2)
return 0;
if(k>prices.size()/2){
for(int i=1; i<prices.size(); i++)
maxProfit += max(prices[i]-prices[i-1], 0);
return maxProfit;
}

int hold[k+1];
int rele[k+1];
for (int i=0;i<=k;++i){
hold[i] = INT_MAX;
rele[i] = 0;
}

for(int i=0; i<prices.size(); i++){
for(int j=k; j>=1; j--){
rele[j] = max(rele[j], prices[i]-hold[j]);
hold[j] = min(hold[j], prices[i]-rele[j-1]);
maxProfit=max(maxProfit, rele[j]);
}
}
return maxProfit;
}
};
``````

At the end, thanks for your sharing, this is a wonderful solution!

• simple case is very useful for my TLE codes ...thanks

• Acturally, do not need to let k>=n-1. If you do n-1 transactions in n days, then the prices must be non-decreasing. For n days, we do at most n/2 transactions, when the size of longest increasing sequenen is just 2. That is 1 3 1 2 1 4... , something like this. If there is an increasing sequenen which is longer than 2, we just need once transaction.

Thanks for you explination.

• Great solution!!!

• still have trouble to figure out the logic that rele[k] is always the right answer, why not some random rele[i]? Why rele[i] is always greater than or equal to rele[i-1]?

Maybe it's better to understand if knowing what is the meaning of rele[i].

Thanks.

• If the test point with \$k=1000000000\$ is changed to \$k=5000\$, the answer would actually be TLE...

I am a little confused about what the test cases are trying to test now

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.