An easy to understand java solution


  • 0
    S

    public class Solution {
    public int rob(int[] nums) {
    int len = nums.length;

        if(len < 1)
            return 0;
        
        if(len < 2)
            return nums[0];
        
        int[] maxM = new int[len];
        boolean[] stolen = new boolean[len];
        int i,j;
        
        maxM[0] = 0;
        stolen[0] = false;
        maxM[1] = nums[1];
        stolen[1] = true;
        
        for (i=2;i<len;i++) {
            if (!stolen[i - 1]) {
                maxM[i] = maxM[i - 1] + nums[i];
                stolen[i] = true;
            } else {
                if (maxM[i - 2] + nums[i] > maxM[i - 1]) {
                    maxM[i] = maxM[i - 2] + nums[i];
                    stolen[i] = true;
                } else {
                    maxM[i] = maxM[i - 1];
                    stolen[i] = false;
                }
            }
        }
        
        int result = maxM[len - 1];
        
        maxM[0] = nums[0];
        stolen[0] = true;
        maxM[1] = nums[0];
        stolen[1] = false;
        
        for (i=2;i<len - 1;i++) {
            if (!stolen[i - 1]) {
                maxM[i] = maxM[i - 1] + nums[i];
                stolen[i] = true;
            } else {
                if (maxM[i - 2] + nums[i] > maxM[i - 1]) {
                    maxM[i] = maxM[i - 2] + nums[i];
                    stolen[i] = true;
                } else {
                    maxM[i] = maxM[i - 1];
                    stolen[i] = false;
                }
            }
        }
        
        if(maxM[len - 2] > result)
            result = maxM[len - 2];
        
        return result;
    }
    

    }


Log in to reply
 

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