Easy java solution with comment


  • 0
    public class Solution {
        public int rob(int[] nums) {
            if(nums==null || nums.length==0) return 0;
            if(nums.length==1) return nums[0];
            
            int len = nums.length;
            int[] dp = new int[len+1];
            // case1: have first one not have last one
            int case1 = 0;
            int case2 = 0;
            dp[0] = 0;
            dp[1] = nums[0];
            for(int i=2; i<=len-1; i++){ // attention: len-1
                dp[i] = Math.max(dp[i-2]+nums[i-1], dp[i-1]);
            }
            case1 = dp[len-1]; // attention: len-1
            // case2: have last one not have first one
            dp[0] = 0;
            dp[1] = 0;
            for(int i=2; i<=len; i++){ // attention: len
                dp[i] = Math.max(dp[i-2]+nums[i-1], dp[i-1]);
            }
            case2 = dp[len]; // attention: dp[len] not dp[len-1] as case1
            return Math.max(case1,case2);
            
        } }

Log in to reply
 

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