Time Limit Exceeded


  • 0
    J

    Can anyone help me ?

    My solution is:
    break the prices array into two parts: partLeft and partRight ;
    maxprofit = (maxprofit, PartLeft_maxprofit + PartRight_maxprofit) ;
    in partLeft or partRight, I just compute at most one transaction which is the stock problem I

              the complexity  I thought is O(n^2),  Is it too slow for this problem???  
    

    now I need help to tell me whether my idea is too slow, or there's something wrong with my codes

    Thanks too much !!! appreciate someone's help

    my codes as follows:

    int maxProfit(vector<int> &prices) {
        int maxProfit = 0;
    	vector<int>::iterator begin = prices.begin();
    	vector<int>::iterator last = prices.end();
    	last--;
    	for(vector<int>::iterator iter=begin;iter!=prices.end();iter++)
    	{
    		int profit;
    		if(iter == last) profit = maxCurrentProfit(begin,last);
    		else profit = maxCurrentProfit(begin,iter)+maxCurrentProfit(++iter,last);
    		if(profit>maxProfit) maxProfit = profit;
    	}
    	return maxProfit;
    }
    
    int maxCurrentProfit(vector<int>::iterator begin,vector<int>::iterator end) {
        int maxProfit = 0;
        if(begin!=end)
        {
    	   int minPrice = *begin;
    	   vector<int>::iterator iter = begin;
    	   for(iter++; iter!=end;iter++){
    		    if((*(iter)-minPrice) > maxProfit)  maxProfit = *(iter)-minPrice;
    		    else if(minPrice > *(iter)) minPrice = *(iter);
    	   }
         }
         return maxProfit;
     }

  • 0
    X

    Actually, the problem can be solved in O(n) complexity


Log in to reply
 

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