x 213. House Robber II

213. House Robber II

time: O(N)

space: O(1)

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
    if (nums.length === 1) return nums[0];
    if (nums.length < 3) return Math.max(nums[0], nums[1]);

    let answer = -Infinity;

    let first = Math.max(nums[0], 0);
    let second = Math.max(nums[1], first);

    for (let i = 2; i < nums.length - 1; i++) {
        const curr = nums[i];
        const temp = second;
        second = Math.max(second, first + curr);
        second = Math.max(second, curr);
        first = temp;
    }
    answer = Math.max(second, answer);

    first = 0
    second = Math.max(nums[1], first);
    for (let i = 2; i < nums.length; i++) {
        const curr = nums[i];
        const temp = second;
        second = Math.max(second, first + curr);
        second = Math.max(second, curr);
        first = temp;
    }
    answer = Math.max(second, answer);

    return answer;
};

time: O(N)

space: O(N)

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (nums.length === 1) return nums[0];
    if (nums.length < 3) return Math.max(nums[0], nums[1]);
    
    let sums = new Array(nums.length).fill(0);
    sums[0] = Math.max(nums[0], 0);
    sums[1] = Math.max(nums[1], sums[0]);
    sums[2] = Math.max(nums[2] + sums[0], sums[1]);

    for (let i = 3; i < nums.length - 1; i++) {
        const curr = nums[i];
        sums[i] = Math.max(sums[i - 2] + curr, sums[i - 1]);
        sums[i] = Math.max(sums[i], curr);
    }
    const odd = sums[nums.length - 2];

    sums = new Array(nums.length).fill(0);
    sums[0] = 0
    sums[1] = Math.max(nums[1], 0);
    for (let i = 2; i < nums.length; i++) {
        const curr = nums[i];
        sums[i] = Math.max(sums[i - 2] + curr, sums[i - 1]);
        sums[i] = Math.max(sums[i], curr);
    }
    const even = sums[nums.length - 1];

    return Math.max(odd, even);
};

// 1 5 -2 1
// 3 5 3 1
// 1 2 3 4
// 4 3 2 1
// 10 1 1 1
// 1 1 1 10
// 1 10 1 1
// 1 1 10 1