Getting "run time" error for very large value of "k" transactions. Can anyone tell me where is the problem ?


  • 0
    S
    class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
            int n=prices.size();
            
            if (n<2)
              return 0;
            vector<vector<int>>T(k+1,vector<int>(n,0));
            
            for (int i=1; i<=k; i++)
            {
                int maxdiff=-prices[0];
                for (int j=1; j<n; j++)
                {
                    T[i][j]=max(T[i][j-1], prices[j]+maxdiff);
                    maxdiff=max(maxdiff, T[i-1][j]-prices[j]);
                }
            }
            return T[k][n-1];
        }
    };

  • 0
    L

    For very large k (for example, k=10 0000 0000), the array consumes too large a memory, which may exceed the limit of the OJ.


Log in to reply
 

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