Don't need DP to solve it within O(n)


  • 15
    S

    Don't need DP to solve this problem. It is still O(n) and basically use the same algorithm solving "Stock I" four times.

    1. Get the max profit with one transaction to the full array. Keep down the start and end positions.

    2. the start and end positions will be included in the result of two transaction. It falls into two categories:
      A) it is one full transaction, B) they belong to two separate transactions(start belongs to first transaction and end belongs to second transaction).

    3. if A)-- get max profit with one transaction to subarray from 0 to start ; get max profit with one transaction to subarray from end to prices.length.

    4. if B)-- get the max profit with one transaction within start and end in reverse order

    5. return the max profit in those cases.


  • 0
    P

    sorry, I don't know how to get two separate transactions within O(n) time in your step 4.


  • -2
    D

    I agree,this is my solution .but I'm confused by the runtime error.

       int maxProfit(vector<int> &prices)
       {
    	if(prices.size()<=1)
    		return 0;
    	int p[2];
    	int maxp=0;
    	int i=0,j=0;
    	int inter;
    	int left;
    	int right;
    	maxp=maxhelper(0,prices.size()-1,prices,p);
    	i=p[0];
    	j=p[1];
    	inter=minhelper(i,j,prices);
    	inter=-inter;
    	
    	left=maxhelper(0,i,prices,p);
    	right=maxhelper(j,prices.size()-1,prices,p);
    	if(inter<left)
    		inter=left;
    	if(inter<right)
    		inter=right;
    	return maxp+inter;
    	
        
        }
    int maxhelper(int start,int end,vector<int> &prices,int *p)
    {
    	if(start>=end)
    		return 0;
    	int minp=0;
    	int *backmin=new int[end-start+1];
    	backmin[end]=prices[end];
    	int i;
    	for(i=end-1;i>=start;i--)
    	{
    		backmin[i]=prices[i]>backmin[i+1]?prices[i]:backmin[i+1];
    	}
    	int hindex;
    	int lindex=start;
    	for(i=start;i<=end;i++)
    	{
    		int temp=backmin[i];
    		int dif=temp-prices[i];
    		
    		if(minp<dif)
    		{
    			minp=dif;
    			lindex=i;
    		}
    	}
    	p[0]=lindex;
    	for(i=lindex;i<=end;i++)
    	{
    		if(prices[i]==backmin[lindex])
    		{	
    			p[1]=i;
    			break;
    		}
    	}
    	
    	return minp ;
    }
    int minhelper(int start,int end,vector<int> &prices)
    {
    	if(start>=end)
    		return 0;
    	int minp=0;
    	int *backmin=new int[end-start+1];
    	backmin[end]=prices[end];
    	int i;
    	for(i=end-1;i>=start;i--)
    	{
    		backmin[i]=prices[i]<backmin[i+1]?prices[i]:backmin[i+1];
    	}
    	for(i=start;i<=end;i++)
    	{
    		int dif=backmin[i]-prices[i];
    		
    		if(minp>dif)
    		{
    			minp=dif;
    			
    		}
    	}
    	return minp;	
    }

  • 0
    S

    I am not sure how your algorithm would work without DP, since you have omitted the most important part, i.e. Step 4. In my understanding, what you meant in Step 4 is:

    find index 'mi' and 'mj' such that 
    
    prices[start, mi] = max(prices[start, i]) for i = (start, end) and
    prices[mj, end] = max(prices[j, end]) for j = (start, end).
    

    This, unfortunately, is not a valid solution if (mi > mj). For example, it
    would not work for sequence like

    [0 2 3 1 4 3 8].

    In the above sequence, the first max-profit transaction [start, mi] is [0 2 3 1 4], and the second one [mj, end] is [1 4 3 8]. However, there is clearly an overlap between these two transactions.

    Maybe I have completely misunderstood your solution. Could you please elaborate on it?


  • 0
    S

    Hey serllari,

    Sorry about the confusion, I mean you first treat the problem as "sell stock I". In your example, you will find the interval between 0 and 8. then the problem fall into "case B". which means 0 belong to first transaction and 8 belong to second transaction. Thus we only need to find a max(end) for the first transaction and a min(start) for the second transaction — Now the problem become “ find max loose in interval 0-8 , which is solve stock I reversely within the interval 0-8.


  • 0
    S

    use the same idea you solve "Stock I" but just do it in reverse order.


  • 0
    S

    Oh now I see what you mean. This indeed works. Thank you for sharing this clever solution! Although the original post could really use some clarification and maybe a good example too.


  • 0
    V

    yes, my code can pass the test without dp.

    public class Solution {
        public int maxProfit(int[] prices) {
            
        	if (prices.length<2) {
        		return 0;
        	}
        	
        	int profit = 0;
        	int candidateIndexLow = 0,indexLow=0, indexHigh=0;
        	int lowestPrice = prices[0];
        	int maxprofit0 = 0;
        	for (int i =1; i < prices.length; i++) {
        		if (prices[i] < lowestPrice) {
        			lowestPrice = prices[i];
        			candidateIndexLow = i;
        		}
        		
        		if (prices[i] - lowestPrice > maxprofit0) {
        			maxprofit0 = prices[i] - lowestPrice;
        			indexHigh = i;
        			indexLow = candidateIndexLow;
        		}
        	}
        	
        	int leftMaxProfit = maxProfitInRange(prices, 0, indexLow-1);
        	int rightMaxProfit = maxProfitInRange(prices, indexHigh+1, prices.length-1);
        	int insideMaxProfit = maxProfitInRange2(prices, indexLow +1, indexHigh -1);
        	
        	int maxOne = Math.max(leftMaxProfit, rightMaxProfit);
        	maxOne = Math.max(maxOne, insideMaxProfit);
        	profit = maxprofit0 + maxOne;
        	
        	return profit;
        }
        
        public int maxProfitInRange2(int[] prices, int startIdx, int endIdx) {
        	// reverse
        	
        	if (startIdx>=endIdx) {
        		return 0;
        	}
        	
        	int profit = 0;
        	int lowestPrice = prices[endIdx];
        	for (int i = endIdx-1; i>=startIdx; i--) {
        		if (prices[i]<lowestPrice) {
        			lowestPrice = prices[i];
        		}else{
        			profit = Math.max(prices[i]-lowestPrice, profit);
        		}
        	}
        	return profit;
        }
        
        
        public int maxProfitInRange(int[] prices, int startIdx, int endIdx) {
        	if (endIdx<0) {
        		return 0;
        	}
        	if (startIdx>=prices.length) {
        		return 0;
        	}
        	int profit = 0;
        	int lowestPrice = prices[startIdx];
        	for (int i =startIdx+1;i<=endIdx;i++) {
        		if (prices[i]<lowestPrice) {
        			lowestPrice = prices[i];
        		}else{
        			profit = Math.max(prices[i]-lowestPrice, profit);
        		}
        	}
        	return profit;
        }
    }

  • 0
    H

    Here is my solution which takes 48ms to pass the test.
    The main idea of my solution is "when I have a third slope, trying to find the best two slopes, and if the first two slopes are the best two, then record the third one in memory".
    The code is long but goes well.

    class Solution {
    private:
        struct Slope
        {
            int buy;
            int sell;
        };
        bool besttwo(Slope slo[3])
        {
            int max;
            int v;
            int id = 0;
            max = slo[0].sell - slo[0].buy + slo[1].sell - slo[1].buy;
            v = slo[1].sell - slo[1].buy + slo[2].sell - slo[2].buy;
            if(max < v)
            {
                max = v;
                id = 1;
            }
            v = slo[1].sell - slo[0].buy + slo[2].sell - slo[2].buy;
            if(max < v)
            {
                max = v;
                id = 2;
            }
            v = slo[0].sell - slo[0].buy + slo[2].sell - slo[1].buy;
            if(max < v)
            {
                max = v;
                id = 3;
            }
            v = slo[0].sell - slo[0].buy + slo[2].sell - slo[2].buy;
            if(max < v)
            {
                max = v;
                id = 4;
            }
            switch(id)
            {
            case 0:
                return true;
            case 1:
                slo[0] = slo[1];
                slo[1] = slo[2];
                return false;
            case 2:
                slo[0].sell = slo[1].sell;
                slo[1] = slo[2];
                return false;
            case 3:
                slo[1].sell = slo[2].sell;
                return false;
            case 4:
                slo[1] = slo[2];
                return false;
            }
        }
    public:
        int maxProfit(vector<int> &prices) {
            int profit = 0;
            int inc = 0;
            int start = 0, end = 0;
            bool flag = true;
            int cnt = 0;
            Slope slo[3] = {};
            for(int i = 1;i < prices.size(); i ++)
            {
                if(flag)
                {
                    if(prices[i] > prices[i-1])
                    {
                        start = i - 1;
                        flag = false;
                    }
                }
                else
                {
                    if(prices[i] < prices[i-1])
                    {
                        flag = true;
                        end = i - 1;
                        switch(cnt)
                        {
                        case 0:
                        case 1:
                            slo[cnt].buy = prices[start];
                            slo[cnt].sell = prices[end];
                            cnt ++;
                            break;
                        case 2:
                            slo[2].buy = prices[start];
                            slo[2].sell = prices[end];
                            if(besttwo(slo))
                                cnt ++;
                            break;
                        case 3:
                            if(prices[start] < slo[2].buy)
                            {
                                slo[2].buy = prices[start];
                                slo[2].sell = prices[end];
                            }
                            else if(prices[end] > slo[2].sell)
                            {
                                slo[2].sell = prices[end];
                            }
                            else break;
                            if(!besttwo(slo))
                                cnt --;
                            break;
                        }
                    }
                }
            }
            if(!flag)
            {
                end = prices.size() - 1;
                switch(cnt)
                {
                case 0:
                case 1:
                    slo[cnt].buy = prices[start];
                    slo[cnt].sell = prices[end];
                    cnt ++;
                    break;
                case 2:
                    slo[2].buy = prices[start];
                    slo[2].sell = prices[end];
                    if(besttwo(slo))
                        cnt ++;
                    break;
                case 3:
                    if(prices[start] < slo[2].buy)
                    {
                        slo[2].buy = prices[start];
                        slo[2].sell = prices[end];
                    }
                    else if(prices[end] > slo[2].sell)
                    {
                        slo[2].sell = prices[end];
                    }
                    else break;
                    if(!besttwo(slo))
                        cnt --;
                    break;
                }
            }
            return slo[0].sell - slo[0].buy + slo[1].sell - slo[1].buy;
        }
    };

  • 0
    N

    I don't understand step 4, why just go through start to end in reverse order, which is max lose? thanks for your answer~


  • 0
    Z

    In case someone else gets confused: "find max loose" is meant to be "find max loss". Great solution nevertheless.


  • 1
    K

    this algo doesn't look right, using above sample and add two more entries: [0 2 3 1 4 3 8 1 7], obviously [0,8] is the single max, however the max of two transactions is [0,8] and [1,7], out of [0,8] for sure. simply [start,end] is not the only interval


  • 0
    D

    My solution is very similar, though I think maybe it could be explained this way:

    1. Every transaction cover a time start from buy, end at sell. Any other transaction need to happen outside this time frame to avoid conflict.

    2. Get buy and sell position as [buy_1, sell_1] for full scan of (0, end). The two point of this transaction split the whole time range to 3 sections:

      left: [0, buy_1 -1] transaction_1: [buy_1, sell_1] right: [sell_1 +1, end]
      * I'm using [] to indicate all indice are inclusive

    3. If we can only do 1 transaction, trans_1 get max profit. If we can do one more, it could be:

      A. pick up an uptick in left or right section, so total = trans_1 + max(left, right)

      B. if there is a downtick in trans_1, we can now sell before the drop, buy before increase, thus avoid this drop, increase total profit. Now we need to find the largest drop inside trans_1, which could be done by either

      a. reverse the section, record the max "increase" which is actual drop. But the index in this section no longer match original index.
      
      b. negative all values of the section, this way the index still count.
      

    I choose the method of negative because my function of scan take indice instead of copy of input, so I can apply the scan function 4 times with less overhead.


  • 0
    E

    yeah i have exactly the same idea and time is 8ms.

    int maxProfit(vector<int>& prices, int start, int end, int dir = 1) {
        int res = 0, mini = prices[start];
        int i = start;
        while (i != end) {
          if (prices[i] < mini) {
            mini = prices[i];
          } else {
            if (prices[i] - mini > res) res = prices[i] - mini;
          }
          i += dir;
        }
        return res;
      }
    
      int maxProfit(vector<int>& prices) {//secret lay in the max and min prices
        int n = prices.size();
        if (n == 0) return 0;
        int minind = 0, tmpind = 0, maxind = 0, res = 0, tmp;
        int mini = prices[0];
        for (int i = 1; i < n; i++) {
          if (prices[i] <= mini) {
            mini = prices[i];
            tmpind = i;
          }
          else {
            tmp = prices[i] - mini;
            if (tmp > res) {
              res = tmp;
              maxind = i;
              minind = tmpind;
            }
          }
        }
        int m = 0, m1, m2;
        if (minind > 1) m = maxProfit(prices, 0, minind);
        m1 = res + m;
        if (maxind < n - 2) m = maxProfit(prices, maxind + 1, n);
        m2 = res + m;
        if (minind < maxind - 2) res += maxProfit(prices, maxind - 1, minind, -1);
    
        return max(max(m1, m2), res);
      }

  • 0
    P

    Very good solution.

    But I think that step 4 can be clearer. It really took much time to be understood.


  • 0

    well, after step 1, you know the start and the end, and notice that there is no element before the start smaller than the start, also, there is no element bigger than the end!


Log in to reply
 

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