Java divide and conquer way


  • 0
    K

    Although I have also implement a dp method which is better than this one. It's fun to use another way of solving it.

    Need to consider both the left part and right part within each section.

    class Solution {
        public int rob(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int res = 0;
    
            res = max(count(nums, 0, nums.length - 1));
            return res;
    
        }
    
        public int max(int[] nums) {
            int max = nums[0];
            for (int i : nums) {
                if (max < i) {
                    max = i;
                }
            }
            return max;
        }
    
        public int max(int digit1, int digit2, int digit3) {
            return Math.max(Math.max(digit1, digit2), digit3);
        }
    
        //left right both neither
        //left means only left part
        //right means only right part
        //return int[] to store each information.
        public int[] count(int[] nums, int start, int end) {
            int[] result = new int[4];
            System.out.println(start + " " + end);
            if (start == end) {
                result[2] = nums[start];
                return result;
            }
    
            int mid = start + (end - start) / 2;
            int[] part1 = count(nums, start, mid);
            int[] part2 = count(nums, mid + 1, end);
            //left = both + neither / left + left / left + neither
            result[0] = max(part1[2] + part2[3], part1[0] + part2[0], part1[0] + part2[3]);
            //right = neither + both / right + right / neither + right
            result[1] = max(part1[3] + part2[2], part1[1] + part2[1], part1[3] + part2[1]);
            //both = left + right / both + right / left + both
            result[2] = max(part1[0] + part2[1], part1[2] + part2[1], part1[0] + part2[2]);
            //neither = neither + neither/ right + neither / neither + left
            result[3] = max(part1[3] + part2[3], part1[1] + part2[3], part1[3] + part2[0]);
            return result;
        }
    
    
    }
    

Log in to reply
 

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