Get Wrong Answer when judge one of test cases BUT it is the same as expected output on my LOCAL ENV


  • 0
    S

    Get Wrong Answer when judge one of test cases BUT it is the same as expected output on my LOCAL ENV.

    The test case can like as follow:

    • Input: [1,2]
    • Output: 0
    • Expected: 1

    Then Please refer my source code:

    class Solution{
    public:
    	int maxProfit(vector<int> &prices){
    		int psize=prices.size();
    		if(psize<2)
    			return 0;
    		vector<int> l(psize);
    		vector<int> r(psize);
    
    		/*solve by DP*/	
    		l[0]=0;
    		r[psize-1]=0;
    
    		int lminv=prices[0];
    		int rmaxv=prices[psize-1];
    		for(int j=1;j<psize;++j){
    			//subfunction get best profit by once
    			// [front,tail]
    
    			//left part solution
    			if(prices[j]<lminv){
    				lminv=prices[j];
    				l[j]=l[j-1];
    			}
    			else{
    				int tprt=prices[j]-lminv;
    				if(tprt<=l[j-1])
    					l[j]=l[j-1];
    				else
    					l[j]=tprt;
    			}
    			//right part solution	
    			int rfront=psize-1-j;	
    			if(prices[rfront]>rmaxv){
    				rmaxv=prices[rfront];
    				r[rfront]=r[rfront+1];
    			}
    			else{
    				int tprt=rmaxv-prices[rfront];
    				if(tprt<=r[rfront])
    					r[rfront]=r[rfront+1];
    				else
    					r[rfront]=tprt;
    			}	
    		}
    		int bstprt=0;
    		for(int i=0;i<psize;++i){
    			bstprt=max(bstprt,l[i]+r[i+1]);
    		}
    
    		return bstprt;
    	}
    };
    

    Thank you for your review !


  • 0
    W

    I think something wrong happens here:

    for(int i=0;i<psize;++i){
        bstprt=max(bstprt,l[i]+r[i+1]);
    }
    

    It should be bstprt = max(bstprt, l[i] + r[i]), right? As the l[i] array means the maxProfit before suffix i, while the r[i] means the maxProfit after suffix i. We scan the prices and initialize the l and r, finally combine the left and right condition.

    Glad to share the same idea and here is my version. Hoping it can help you.

    class Solution {
    public:
        int maxProfit(vector<int> &prices) {
            if (prices.size() < 2) {
    			return 0;
    		}
    		// leftMax[i] means the maxProfit before suffix i, while rightMax[i] means the maxProfit after suffix i.
    		vector<int> leftMax(prices.size(), 0), rightMax(prices.size(), 0);
    		int minEle = prices[0], maxEle = prices[prices.size() - 1];
    		for (int idx = 1; idx < prices.size(); ++idx) {
    			if (prices[idx] < minEle) {
    				minEle = prices[idx];
    			}
    			leftMax[idx] = max(leftMax[idx - 1], prices[idx] - minEle);
    
    			int ridx = prices.size() - 1 - idx;
    			if (prices[ridx] > maxEle) {
    				maxEle = prices[ridx];
    			}
    			rightMax[ridx] = max(rightMax[ridx + 1], maxEle - prices[ridx]);
    		}
    		// Combine the leftMax and rightMax.
    		int ret = 0;
    		for (int idx = 0; idx != leftMax.size(); ++idx) {
    			ret = max(ret, leftMax[idx] + rightMax[idx]);
    		}
    		return ret;
        }
    };

  • 0
    S

    Fortunately your idea help me get AC response. However I am sorry that r[i] means maxprofit of [ prices[0], prices[i] ] instead of > before suffix i. From sentence
    leftMax[idx] = max(leftMax[idx - 1], prices[idx] - minEle); we can see prices[i] (or prices[idx]) has been included. In fact ' max(ret, leftMax[idx] + rightMax[idx]);' did not express my right idea but will always get rigtht answer, which can be proved in theory.
    The real problem actually happen in the same part you concern about.
    ' bstprt=max(bstprt,l[i]+r[i+1]); ' has two problems:

    • Out of index happened when scan to the end.

    • Only one trasaction was not included.
      Above problems can be corrected by following code:

                      int bstprt=r[psize-1];
      	for(int i=0;i<psize-1;++i){
      		bstprt=max(bstprt,l[i]+r[i+1]);
      	}
      	if(l[psize-1]>bstprt)
      	    bstprt=l[psize-1];
      

    Appreciate your help and your share.


  • 0
    W

    Glad to know that you have found the point.


Log in to reply
 

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