Java, with explanation


  • 1

    This problem can be treated as "Maximum sum such that no two elements are adjacent" problem: http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/.
    For the ith in the num, we want to get max(num[i]+total[i-2], total[i-1]). total[i-1] means the max value from num[0] to num[i-1]. So here goes:

    public class Solution {
        public int rob(int[] nums) {
            if(nums == null || nums.length == 0)
                return 0;
            if(nums.length == 1)
                return nums[0];
            int[] res = new int[nums.length + 1];
            
            res[0] = 0;
            res[1] = nums[0];
            
            for(int i = 2; i < nums.length + 1; i ++){
                res[i] = Math.max(res[i-1], res[i-2] + nums[i-1]);
            }
            return res[nums.length];
        }
    }
    

Log in to reply
 

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