Simple DP Java O(n) Solution


  • 0
    A
    public class Solution {
        public int rob(int[] nums) {
            int i,max = 0;
            if(nums.length < 3){
                for(i = 0 ;i<nums.length; i++){
                    max = Integer.max(nums[i], max);
                }
                
                return max;
            }
            int res[] = new int[nums.length];
            res[0] = nums[0];
            res[1] = nums[1];
            max = Integer.max(res[0],res[1]);
            for(i = 2; i < nums.length; i++){
                res[i] = Integer.max(res[i-2]+nums[i], res[i-1]-nums[i-1]+nums[i]);
                max = Integer.max(res[i],max);
            }
            System.out.print("[");
            for(i = 0; i< res.length; i++){
                System.out.print(res[i]+" ");
            }
            System.out.println("]");
            return max;
        }
    }

Log in to reply
 

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