class MaximumSubarrayDivideConquer {
public int maxSubArrayDividConquer(int[] nums) {
if (nums == null || nums.length == 0) return 0;
return helper(nums, 0, nums.length - 1);
private int helper(int[] nums, int l, int r) {
if (l > r) return Integer.MIN_VALUE;
int left = helper(nums, l, mid - 1);
int right = helper(nums, mid + 1, r);
// left surfix maxSum start from index mid - 1 to l
for (int i = mid - 1; i >= l; i--) {
leftMaxSum = Math.max(leftMaxSum, sum);
// right prefix maxSum start from index mid + 1 to r
for (int i = mid + 1; i <= r; i++) {
rightMaxSum = Math.max(sum, rightMaxSum);
// max(left, right, crossSum)
return Math.max(leftMaxSum + rightMaxSum + nums[mid], Math.max(left, right));