Share my solution with two DP, one DP exclude first element, the other exclude last element.


  • 1
    K
    public int rob(int[] nums) {
        if(nums.length==0)return 0;
        if(nums.length==1) return nums[0];
        int cur = 0;
        int premax = 0;
        int max_1 = 0;
        int max_2 = 0;
        for(int i = 0;i<nums.length-1;i++)
        {
            max_1 = Math.max(cur+nums[i],premax);
            cur = premax;
            premax = max_1;
        }
        cur = 0;
        premax = 0;
        for(int i =nums.length-1;i>=1;i--)
        {
            max_2 = Math.max(cur+nums[i],premax);
            cur = premax;
            premax = max_2;
        }
        return max_1>max_2?max_1:max_2;
    }

Log in to reply
 

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