213 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.

Solution:

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if ( n == 0 ) return 0;
        if ( n == 1 ) return nums[0];
        if ( n == 2 ) return max(nums[0], nums[1]);


        int rob1, rob2;
        if ( n == 3 ) {
            rob1 = nums[0]; rob2 = max(nums[1], nums[2]);
            return max(rob1, rob2);
        }
        if ( n == 4 ) {
            rob1 = nums[0] + nums[2]; rob2 = nums[1] + nums[3];
            return max(rob1, rob2);
        }
        // assume nums[0] is robbed, nums[1] is not robbed
        // p1 ?-*; p2 -*-; p3 *--
        vector<int> p1(n-4, 0), p2(n-4, 0), p3(n-4, 0);
        p1[0] = nums[0] + nums[2] + nums[4];
        p2[0] = nums[0] + nums[3];
        p3[0] = nums[0] + nums[2];
        for ( int i = 1; i <= n-5; i++ ) {
            p1[i] = max(p2[i-1], p3[i-1]) + nums[i+4];
            p2[i] = p1[i-1];
            p3[i] = p2[i-1];
        }
        rob1 = max(p2[n-5], p3[n-5]);
        // assume nums[0] is not robbed;
        vector<int> q1(n-3, 0), q2(n-3, 0), q3(n-3, 0);
        q1[0] = nums[1] + nums[3];
        q2[0] = nums[2];
        q3[0] = nums[1];
        for ( int i = 1; i <= n-4; i++ ) {
            q1[i] = max(q2[i-1], q3[i-1]) + nums[i+3];
            q2[i] = q1[i-1];
            q3[i] = q2[i-1];
        }
        rob2 = max(q1[n-4], max(q2[n-4], q3[n-4]));
        return max(rob1, rob2);
    }
};