House Robber II

Question:
http://www.lintcode.com/en/problem/house-robber-ii/
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Answer:
~~~c++
class Solution {
public:
     /*
     * @param nums: An array of non-negative integers.
     * @return: The maximum amount of money you can rob tonight
     */
    int houseRobber2(vector<int> nums) {
        if (nums.size() <= 1)
            return nums.empty() ? 0 : nums[0];
        vector<int> nums_inf = nums;
        vector<int> nums_inl = nums;
        nums_inf.pop_back();
        nums_inl.erase(nums_inl.begin());
        return max(houseRobber(nums_inf), houseRobber(nums_inl));
    }

    /*
     * @param A: An array of non-negative integers
     * @return: The maximum amount of money you can rob tonight
     */
    long long houseRobber(vector<int> &A) {
        size_t as = A.size();
        if (as == 0)
          return 0;
        if (as == 1)
          return A[0];
        if (as == 2)
          return max(A[0], A[1]);
        vector<long long> dp(as);
        dp[0] = A[0];
        dp[1] = max(A[0], A[1]);
        for (size_t i = 2; i < as; i++)
          dp[i] = max(dp[i-1], dp[i-2] + A[i]);
        return dp[as-1];
    }
};
~~~

PS:
if houseRobber(vector<int> &A) use memory O(1) method in [house-robber](http://acm.errong.win/house-robber/),
   
~~~c++
    long long houseRobber(vector<int> &A) {
        size_t as = A.size();
        long long odd, even;
        odd = even = 0;
        for (size_t i = 0; i < as; i++)
          if (i % 2)
            odd = max(odd+A[i], even);
          else
            even = max(even + A[i], odd);
        return max(odd, even);
    }
~~~

houseRobber2 will exceed the time limit.
it seems like i%2 operation will take more time.

❤️ Support This Blog

---

If this post helped you, you can support my writing with a small donation. Thank you for reading.

---

Coffee ☕ Thanks 🙏 Extra Support ❤️