# Twice pass solution, C++

• Twice pass:

1. not rob nums[n-1]
2. not rob nums[0]

and the other is same as House Robber.

``````int rob(vector<int>& nums)
{
if(nums.size() == 0)
return 0;
if(nums.size() == 1)
return nums[0];

int pre1 = 0, cur1 = 0;
for(int i = 0; i < nums.size() - 1; ++ i)
{
int temp = pre1;
pre1 = cur1;
cur1 = max(temp + nums[i], pre1);
}

int pre2 = 0, cur2 = 0;
for(int i = 1; i < nums.size(); ++ i)
{
int temp = pre2;
pre2 = cur2;
cur2 = max(temp + nums[i], pre2);
}

return max(cur1, cur2);
}``````

• clever code. But the explanation seems confused. Maybe this is better:

1. not rob num[0]
2.not rob num[n-1]
Note that num[0] and num[n-1] can't robbed at the same time, so the division is complete.

• The same idea with you

`````` class Solution {
public:
// start is 0 or 1
int work(vector<int> &nums, int start) {
int n = nums.size();
if (n < start + 1) return 0;
if (n == start + 1) return nums[start];
if (n == start + 2) return max(nums[start], nums[start+1]);
if (start == 0)
--n;
vector<int> dp(n, 0);
dp[start] = nums[start];
dp[start+1] = max(nums[start], nums[start+1]);
for (int i = start+2; i < n; i++)
dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
return dp.back();
}

int rob(vector<int>& nums) {
if (nums.size() == 0) return 0;
return max(work(nums, 0), work(nums, 1));
}
};``````

### Are they adjacnet?

• oh, aha, yes, rob nums[0] means not rob nums[n-1]

• If the length of the array is two, then cur1 will be nums[0] and cur2 will be nums[1], so the answer is max(cur1, cur2).

### Am I right?

• I came up with a very similar two pass solution. I just modified my House Robber I solution to force robbing the 0th house (or not). Some special care needs to be taken on last house, depending on whether I robbed 0th house or not.

``````class Solution {
public:
//if force0Rob is true,  I HAVE to     rob 0-th house
//if force0Rob is false, I HAVE to NOT rob 0th house
int robPrime(vector<int>& nums, bool force0Rob) {

//dynamic programming cache; money made by robbing *optimal choices* of houses until index i
vector<int> money(nums.size(), 0);
money[0] = force0Rob ? nums[0] : 0;
money[1] = force0Rob ? nums[0] : nums[1];

//dynamic programming loop
for (int i=2; i<nums.size()-1; i++) {
int cand1 = nums[i] + money[i-2];
int cand2 = money[i-1];
money[i] = cand1 > cand2 ? cand1 : cand2;
}

//last place
int last = nums.size() - 1;
int lastbutone = nums.size() - 2;
int lastbuttwo = nums.size() - 3;
money[last] = force0Rob ? (max(money[lastbutone], money[lastbuttwo]))
: (max(money[lastbutone], money[lastbuttwo] + nums[last]));
return money[last];
}
int rob(vector<int>& nums) {
if (nums.size() == 0) return 0;
if (nums.size() == 1) return nums[0];
if (nums.size() == 2) return max(nums[0], nums[1]);
return (max(robPrime(nums, true), robPrime(nums, false)));
}
}; ``````

• The optimal solution may be not rob 0 and not rob n-1. Division "rob 0" and "not rob 0" may not cover the optimal solution. Rob 0 should be num[0] + HouseRobber(num[2...n-2]).
But your code is correct. Thanks.

• yeah, now I have modify it.

• They are adjacent, so one of them (not both) can be robbed.

• ``````class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 1) return nums[0];
int opt1 = rob1(nums, 0, nums.size() - 2);
int opt2 = rob1(nums, 1, nums.size() - 1);
//cout << opt1 << " " << opt2 << endl;
return max(opt1, opt2);
}
int rob1(vector<int>& nums, int start, int end) {
if (end < start) return 0; //edge case
vector<int> result;
for (int i = start; i <= end; i++){
if (i == start) result.push_back(nums[start]);
else if (i == start + 1) result.push_back(max(nums[start+1], nums[start]));
else{
result.push_back(max(result[result.size() - 1], result[result.size() - 2] + nums[i]));
}
}
return result[result.size() - 1];
}
};
``````

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