EASY UNDERSTAND RECURSIVE SOLUTION(JAVA)


  • 0
    M
    public class Solution {
        public int rob(int[] nums) {
            return foo(nums,0,nums.length-1);
        }
        public int foo(int[] nums,int start,int end){
            if(start>end)return 0;
            if(start==end)return nums[start];
            int mid=start+(end-start)/2;
            //nums[mid] is robed
            int tmp1=foo(nums,start,mid-2)+foo(nums,mid+2,end)+nums[mid];
            //nums[mid] is not robed
            int tmp2=foo(nums,start,mid-1)+foo(nums,mid+1,end);
            return Integer.max(tmp1,tmp2);
        }
    }
    

Log in to reply
 

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