My easy to understand Java Solution O(n) time, O(1) space.

  • 0

    public int rob(int[] nums) {
    if (nums == null || nums.length == 0) return 0;

        //Dynamic programming. Compute max bottom up.
        int maxN = nums[0]; //Max for the nth house
        int maxNminus1 = 0; //Max up to house n-1
        int maxNminus2 = 0; //Max up to house n-2
        maxNminus1 = maxN; //Advance to the next house
        for (int n = 1; n< nums.length; n++) {
            //Compute new max for nth house
            //If we robbed previous house, it's mn1.
            //If we didn't rob previous house, it's nums[n] + mn2
            maxN = Math.max(maxNminus1, nums[n] + maxNminus2);
            maxNminus2 = maxNminus1;
            maxNminus1 = maxN;
        return maxN;


Log in to reply

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