198. House Robber

/**
 * Iterative Solution
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(1)
 *
 * N = Length of input nums array
 */
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        int previousMax = 0, currentMax = 0;
        for (int num : nums) {
            int temp = currentMax;
            currentMax = Math.max(previousMax + num, currentMax);
            previousMax = temp;
        }

        return currentMax;
    }
}

/**
 * Recursive Solution. This solution gives time limit exceeded.
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(N) - Recursion stack
 *
 * N = Length of the input nums array.
 */
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return robHelper(nums, nums.length - 1);
    }

    private int robHelper(int[] nums, int i) {
        if (i < 0) {
            return 0;
        }
        return Math.max(robHelper(nums, i - 2) + nums[i], robHelper(nums, i - 1));
    }
}