Java O(N)Time O(1)Space


  • 0
    T

    For house i, the previous house you want to try is house i-2 or i-3.

    What about house i-4? It is must smaller than inheriting from i-2(because the money is non-negative)

    What about house i-5? It is must smaller than inheriting from i-3(because the money is non-negative)

    Right?

    public class Solution {
        public int rob(int[] nums) {
            if(nums == null || nums.length == 0){
                return 0;
            }else if (nums.length == 1){
                return nums[0];
            }else if (nums.length == 2){
                return Math.max(nums[0], nums[1]);
            }
            
            for(int i = 2; i < nums.length; i++){
                nums[i] += i == 2 ? nums[0] : Math.max(nums[i - 2], nums[i - 3]);
            }
            
            return Math.max(nums[nums.length - 1], nums[nums.length - 2]);
        }
    }
    

Log in to reply
 

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