House Robber II

Problem

You are given an integer array nums where nums[i] represents the amount of money the ith house has. The houses are arranged in a circle, i.e. the first house and the last house are neighbors.

You are planning to rob money from the houses, but you cannot rob two adjacent houses because the security system will automatically alert the police if two adjacent houses were both broken into.

Return the maximum amount of money you can rob without alerting the police.

Examples

Example 1:

Input: nums = [3,4,3]

Output: 4

Explanation: You cannot rob nums[0] + nums[2] = 6 because nums[0] and nums[2] are adjacent houses. The maximum you can rob is nums[1] = 4.

Example 2:

Input: nums = [2,9,8,3,6]

Output: 15

Explanation: You cannot rob nums[0] + nums[2] + nums[4] = 16 because nums[0] and nums[4] are adjacent houses. The maximum you can rob is nums[1] + nums[4] = 15.

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 200

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the number of houses.

Solution

Current index is the most we can rob up to and including that house. The value for a given index is the maximum of the previous house (since we can’t rob current house if we rob the previous house) and the current house + 2 indices previously.

Because houses are circular, we cannot rob the first and last house. So we split this up into 2 cases:

• Rob houses 0 to n-2 inclusive
• Rob houses 1 to n-1 inclusive

class Solution {
    // Indices inclusive
    int helper(std::vector<int> &nums, int idx_start, int idx_end) {
        if (idx_start == idx_end) { return nums[idx_start]; }
        int prev_prev = nums[idx_start];
        int prev = std::max(prev_prev, nums[idx_start + 1]);
        int curr = prev;
        for (int i = idx_start + 2; i <= idx_end; ++i) {
            curr = std::max(prev, prev_prev + nums[i]);
            prev_prev = prev;
            prev = curr;
        }
        return curr;
    }
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 1) { return nums[0]; }
        return std::max(helper(nums, 0, nums.size() - 2), helper(nums, 1, nums.size() - 1));
    }
};