213. House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

 

Example 1:

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 3:

Input: nums = [0]
Output: 0

 

Constraints:

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

Rust Solution

struct Solution;

impl Solution {
    fn rob(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        if n == 0 {
            return 0;
        }
        if n == 1 {
            return nums[0];
        }
        Self::rob_slice(&nums[0..n - 1]).max(Self::rob_slice(&nums[1..n]))
    }
    fn rob_slice(v: &[i32]) -> i32 {
        let n = v.len();
        let mut prev = 0;
        let mut curr = 0;
        for i in 0..n {
            let temp = curr.max(v[i] + prev);
            prev = curr;
            curr = temp;
        }
        curr
    }
}

#[test]
fn test() {
    let nums = vec![2, 3, 2];
    let res = 3;
    assert_eq!(Solution::rob(nums), res);
    let nums = vec![1, 2, 3, 1];
    let res = 4;
    assert_eq!(Solution::rob(nums), res);
    let nums = vec![0];
    let res = 0;
    assert_eq!(Solution::rob(nums), res);
    let nums = vec![];
    let res = 0;
    assert_eq!(Solution::rob(nums), res);
    let nums = vec![1];
    let res = 1;
    assert_eq!(Solution::rob(nums), res);
}

Having problems with this solution? Click here to submit an issue on github.