Why I get Runtime Error

• I put some custom input and the output is correct.
But I get Runtime error by following C++ code.
the error msg:
Last executed input:
1000000000, [106,373,495,46,359,919,906,440,783,583,784,73,238,701,972,308,165,774,990,675,737,990,713,157,.......
Do I need to reduce space usage?

``````int maxProfit(int k, vector<int>& prices) {
if(k==0||prices.size()<=1){
return 0;
}
vector<vector<int>> f(k+1,vector<int>(prices.size(),0));

for(int kk=1;kk<=k;kk++){
int tmp=f[kk-1][0]-prices[0];
for(int j=1;j<prices.size();j++){
f[kk][j]=max(f[kk][j-1],prices[j]+tmp);
tmp=max(tmp,f[kk-1][j]-prices[j]);
}

}
return f[k][prices.size()-1];
}``````

• See answer of the discuss titled Share my C++ DP solution with O(kn) time O(k) space,

• Do I need to reduce space usage?

Well, you're trying to create a vector with 1000000000+1 vectors of 10000 ints each. That's over 40000 GB. Do you really think that will work?

• I got accept by modify the ksize vector into 2size. Modding by 2 make 2*size.

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

vector<vector<int>> f(2,vector<int>(len,0));
for(int kk=1;kk<=k;kk++){
int tmp=f[(kk-1)%2][0]-prices[0];
for(int j=1;j<len;j++){
f[kk%2][j]=max(f[kk%2][j-1],prices[j]+tmp);
tmp=max(tmp,f[(kk-1)%2][j]-prices[j]);
}
}
return f[k%2][len-1];
/*
vector<vector<int>> f(k+1,vector<int>(prices.size(),0));
for(int kk=1;kk<=k;kk++){
int tmp=f[kk-1][0]-prices[0];
for(int j=1;j<prices.size();j++){
f[kk][j]=max(f[kk][j-1],prices[j]+tmp);
tmp=max(tmp,f[kk-1][j]-prices[j]);
}
}
return f[k][prices.size()-1];*/
}``````

• 12ms now. I still think why someone take the different order like loop kk then inner-loop j.
Is that faster?

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