Share my O(N) Java solution


  • 1
    X
    public class Solution {
        public int rob(int[] num) {
            int len=num.length;
            if(len==0) return 0;
            if(len==1) return num[0];
            if(len==2) return Math.max(num[0],num[1]);
            if(len==3) return Math.max(num[0]+num[2], num[1]);
            int[] dp=new int[len];
            dp[0]=num[0];
            dp[1]=num[1];
            dp[2]=num[0]+num[2];
            for(int i=3;i<len;i++){
                dp[i]=Math.max(dp[i-3]+num[i], dp[i-2]+num[i]);
            }
            return Math.max(dp[len-1], dp[len-2]);
        }
    }

Log in to reply
 

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