# 0ms java solution using dp,O(n) time, with explanation

• let sum[i] be the maximum amount of money when robber comes at i, he can either rob it or not depending on the money robbed at i-1 and i-2.

corner case: sum[0] = num[0], sum[1] = max(num[0],num[1])

generally, at position i, sum[i] = max(sum[i-1], sum[i-2]+num[i])

``````public int rob(int[] nums) {
int size = nums.length;
if(size == 0) return 0;
int[] sum = new int[size];
sum[0] = nums[0];
if(size == 1) return sum[0];
sum[1] = Math.max(sum[0],nums[1]);
if(size == 2) return sum[1];
for(int i = 2;i<size;i++){
sum[i] = Math.max(sum[i-1], sum[i-2]+nums[i]);
}
return sum[size-1];
}
``````

Another approach is to use two variables to store sum[i-1] and sum[i-2] iteratively in the previous program. This approach avoids building an array to store all of the sums, which only uses O(1) space.

``````public int rob(int[] nums) {
int size = nums.length;
if(size == 0) return 0;
if(size == 1) return nums[0];
if(size == 2) return Math.max(nums[0],nums[1]);
int minusOne = Math.max(nums[0],nums[1]), minusTwo = nums[0], sum = minusOne;
for(int i = 2;i<size;i++){
sum = Math.max(minusOne, minusTwo+nums[i]);
minusTwo = minusOne;
minusOne = sum;
}
return sum;
}``````

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