# Some times it is possible to solve this in one pass

• 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);
}
};``````

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