Some times it is possible to solve this in one pass


  • 0
    S

    Well, The basic idea is that, if we are doing the dp from index 0 to n-2, then
    if both n[0] and n[n.size()-2] are not robbed. then we can add n[n.size()-1] then that is the final result.
    and in this case, we don't need to do the second pass from 1 to n-1.

    Here is the AC code, costs 0ms, it is more complicated, and it needs some more space, but, in some of the cases it can be faster.

    class Solution {
    public:
        int rob(vector<int>& n) {
            if(n.size()==0) return 0;
            if(n.size()==1) return n[0];
            if(n.size()==2) return max(n[0], n[1]);
            if(n.size()==3) return max(max(n[0], n[1]), n[2]);
            
            int posRob=0, negRob=0;
            vector<int> dp(n.size(),0);
            vector<bool> robEdge(n.size(), false);
            
            dp[0]=n[0], dp[1]=max(n[0], n[1]);
            robEdge[0]=true;
            robEdge[1]=n[1]<n[0];
            
            int i;
            for(i=2; i<n.size()-1; ++i){
                dp[i]=max(dp[i-1], dp[i-2]+n[i]);
                robEdge[i]=robEdge[i-1];
                if(dp[i]>dp[i-1])   //rob according dp[i-2] path
                    robEdge[i]=robEdge[i-2];
                else if(dp[i-2]+n[i]==dp[i-1])  {// either way is ok, rob n[i] & path from n[i-2] to start, or just rob from n[i-1] path
                    robEdge[i]=robEdge[i-1]&&robEdge[i-2];  // maybe 
                }
    
            }
            
            int tmp1, tmp2;
            
            tmp1=dp[i-1];
            if((robEdge[n.size()-3]==false) && (dp[i-1]==dp[i-2]))  //did not rob the first and (n-1)th then you can rob the last
                return tmp1+n[i];
                
            for(i=0;i<dp.size();++i){
                dp[i]=0;
                robEdge[i]=false;
            }
            
            dp[n.size()-1]=n[n.size()-1]; 
            dp[n.size()-2]=max(n[n.size()-1], n[n.size()-2]);
            
            for(i=n.size()-3;i>0; --i){
                dp[i]=max(dp[i+1], dp[i+2]+n[i]);
            }
            
            tmp2=dp[1];
            
            return max(tmp2,tmp1);
        }
    };

Log in to reply
 

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