Easy to understand solution. Java. O(n) time and space complexity


  • 0
    O
    public class Solution {
        public int rob(int[] nums) {
        	if (nums.length == 0) {
        		return 0;
        	}
        	if (nums.length == 1) {
        		return nums[0];
        	}
            int[] numsSum = new int[nums.length];
            for(int i = nums.length - 1; i >= 0; i--) {
            	if (i+3 < nums.length) {
            		numsSum[i] = Math.max(nums[i] + numsSum[i+2], nums[i] + numsSum[i+3]);
            	} else if(i+2 < nums.length) {
            		numsSum[i] = nums[i] + numsSum[i+2];
            	} else {
            		numsSum[i] = nums[i];
            	}
            }
            return Math.max(numsSum[0], numsSum[1]);
        }
    }

Log in to reply
 

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