O(n) Java solution using DP

  • 9
    public int rob(int[] nums) {
        int len = nums.length;
        if(len == 0) return 0;
        if(len == 1) return nums[0];
        int[] val = new int[len];
        val[0] = nums[0];
        val[1] = Math.max(nums[0], nums[1]);
        for(int i=2; i<len; i++)
            val[i] = Math.max(nums[i] + val[i-2], val[i-1]);
        return val[len-1];

    For each house, the maximum amount you can get is either the amount you get from two houses before this one plus the amount you get from this one, or the amount you get from the neighbor house before this one (so you can't get any from this one), whatever is larger.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.