Time Limit Exceeded


  • 0
    X

    int maxProfit(vector<int>& prices) {

        size_t n = prices.size();
        if(n <= 0) return 0;
        
        int mi = prices[0];
        int mx = prices[n-1];
        
        vector<vector<int>> mdp(n,vector<int>(n,0));
        
        for(int i = 1;i < n; i++)
        {
            mdp[0][i] = max(mdp[0][i-1],prices[i] - mi);
            mi = min(mi,prices[i]);
            
            int m = n-i-1;
            mdp[m][n-1] = max(mdp[m+1][n-1],mx - prices[m]);
            mx = max(mx,prices[m]);
            
            
        }
        
        int rt = mdp[0][n-1];
        for(int i = 1; i < n-1; i++)
        {
            rt = max(rt,mdp[0][i] + mdp[i+1][n-1]);
        }
        
        
        return rt;
        
    }
    

    why Time Limit Exceeded???


Log in to reply
 

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