Java divide and conquer way

• 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;
}

}
``````

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