Is it something with my code, or it is just poor memory management?


  • 0
    R

    I tried to solve this problem with nested loop:

    public int maxProfit(int[] prices) {
            int max = 0;
            for(int i = 0; i<prices.length; i++){
                int buyprice = prices[i];//test the case where buyer buys on the i-th day
                for (int j = i; j<prices.length; j++){
                    int sellprice = prices[j];// test the case where the buyer sells on either the current day or after
                    int profit = sellprice-buyprice;
                    if(profit>=max){
                        max= profit;
                    }
                }
            }
            return max;
        }
    

    And yet what I got is TLE with test case [10000,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990,9989,9988,9987....]
    Can anyone give me a hint what went wrong? Thank you in advance!


  • 4
    Y

    I would like to share my idea with you.
    It is O(n)

    int maxProfit(vector<int> &prices) {
        if(prices.empty()) return 0;
    
        int MaxProfit = 0;
        int max = 0;   //max temp
        
        for(int i=0;i<prices.size()-1;i++){
            prices[i]=prices[i+1]-prices[i];
        } //calculate the gradient
    
        for(vector<int>::iterator count=prices.begin();count<prices.end()-1;count++){
            if(*count >= 0) max += *count;           //trend of increment
            else{ 
                 MaxProfit = MaxProfit > max? MaxProfit : max ;   // Refresh the record
                 max = max + *count > 0 ? max + *count : 0;      // No profit, abandoned
            }
        }
        
        if(MaxProfit < max) return max;          // In case that max happens in the last iteration
        
        return MaxProfit;
    }
    

  • 0
    R

    Thank you! I implemented this in Java and it works perfectly. It is better memory management than nested loop. :)


  • 0
    T

    those for loop could be combined into one

    public int maxProfit(int[] prices) {
    	
    	if (prices.length<2) return 0;
    	
    	int MaxProfit = 0;
    	int max = 0;
    	int p;
    
    	for(int i=0;i < prices.length-1 ; i++){
    		p=(prices[i+1] - prices[i]);
    		if (p >=0) max += p;
    		else{
    			MaxProfit = MaxProfit > max ? MaxProfit: max ;
    			max = max + p > 0 ? max + p : 0 ;
    		}
    	}
    	
    	if (MaxProfit < max) return max;
    	return MaxProfit;
    }
    

  • 3
    Y

    Another solution that is also O(n). I think the code is pretty self-explainary.

    int maxProfit(vector<int> &prices) {
        int profit = 0;
        int lowest = INT_MAX; // lowest stock price up-to-date
        
        for(int i=0;i<prices.size();i++)
        {
            profit = profit<prices[i]-lowest ? prices[i]-lowest : profit;
            lowest = lowest>prices[i] ? prices[i] : lowest; // update the lowest stock price 
        }
        
        return profit;
    }

  • 0
    G

    just by keeping the lowest price and compare prices with the lowest price to calculate highest profit, you can finish this task in O(N), here is my code

    class Solution {
    public:
        int maxProfit(vector<int> &prices) {
            int lowest = numeric_limits<int>::max();
            int maxp = 0;
            for (int i=0; i<prices.size(); ++i) {
                int v = prices[i];
                lowest = min(lowest, v);
                maxp = max(maxp, v - lowest);
            }
            return maxp;
        }
    };
    

Log in to reply
 

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