Why I get Runtime Error


  • 0
    F

    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];
    }

  • -1
    B

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


  • 0

    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?


  • 0
    F

    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];*/
    }

  • 0
    F

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


Log in to reply
 

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