Find maximum sum subarray (Divide and Conquer)
  • 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 Answers

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

You need to Sign In to post your solution.