### Find maximum sum subarray (Divide and Conquer) subarray array general    Posted: 6 years ago Edit answers (1) views (17212)

Suppose you are given a one dimensional array of arbitrary integers. How will you find the maximum sum sub-array using Divide and Conquer?

 Posted: 6 years ago Updated: 6 years ago 0 0 Edit We can find the maximum sum subarray using recursive divide and conquer. The algorithm works as : Divide the array into two parts. Find maximum subarray sum for left half recursively. Find maximum subarray sum for right half recursively. Find maximum subarray sum for the subarray including the middle element. (Sum of last two steps) Return the maximum of the last three results. Time complexity = O(nlogn) . public static int FindMaxSumSubArray(int[] array, int low, int high){ /* No element in the array */ if (low > high) return 0; /* One element in the array */ if (low == high) return max(0, array[low]); /* Middle element of the array */ int middle = (low + high) / 2; /* find maximum sum crossing to left */ leftMax = sum = 0; for (i = middle; i ≥ low; i--) { sum += array[i]; if (sum > leftMax) leftMax = sum; } /* find maximum sum crossing to right */ rightMax = sum = 0; for (i = middle+1; i ≤ high; i++) { sum += array[i]; if (sum > rightMax) rightMax = sum; } /* Return the maximum of leftMax, rightMax and their sum */ return Math.max(leftMax + rightMax, Math.max(FindMaxSumSubArray(low, middle), FindMaxSumSubArray(middle+1, high))); }