I do NOT know how I can design this algorithm and got AC


  • 0
    J

    I just simulate the stock trade process, first buy it and then sale it,
    and after times of try, here comes the AC, unbelievable!

    I wander is there anybody whose code is longer than mine?

        class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int len = prices.size();
            if (len < 2)   return 0;
            
            int buy=-1;
            int sell=-1;
            int min_t=0;
            vector<int> p(len, 0);
            
            p[0] = 0;
            if(prices[1] > prices[0]) 
            {
                p[1] = prices[1] - prices[0];
                buy = 0;
                sell = 1;
            } else {
                p[1] = 0;
                min_t = 1;
            }
            
            for(int i=2; i<len; i++) 
            {
                int pnow = prices[i];
                
                if(buy != -1)//bought stock already
                {
                    if(pnow > prices[sell]) 
                    {
                        if(pnow-prices[sell] >= pnow - prices[min_t]) {
                            p[i] = p[i-1] + (pnow-prices[sell]);
                            sell = i;
                        } else {
                            p[i] = pnow - prices[min_t];
                            sell = i;
                            buy = min_t;
                        }
                    } else { 
                        if(pnow <= prices[min_t])
                            min_t = i;
                        
                        if(pnow - prices[min_t] > p[i-1])
                        {
                            p[i] = pnow - prices[min_t];
                            buy = min_t;
                            sell = i;
                        } else
                            p[i] = p[i-1];
                    }
    
                } else { // not bought yet
                    if(pnow <= prices[min_t]) 
                    {
                        min_t = i;
                        p[i] = p[i-1];
                    } else {
                        sell = i;
                        buy = min_t;
                        p[i] = pnow - prices[buy];
                    }
                }
            }
            
            return p[len-1];
        }
    };

  • 1
    V

    Here is my solution. Basically, you have to keep update the buy price to be the minimum value and calculate profit on basis of that.

    public class Solution {
        public int maxProfit(int[] prices) {
            if(prices.length < 2){
                return 0;
            }
            int profit = 0;
            int buyPrice = prices[0];
            for(int i=1;i<prices.length;i++){
                if(prices[i] < buyPrice){
                    buyPrice = prices[i];
                }
                else{
                    int profitTemp = prices[i] - buyPrice;
                    if(profitTemp>profit){
                        profit = profitTemp;
                    }
                }
            }
            return profit;
        }
    }

Log in to reply
 

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