Maximum Subarray Sum - O(nlogn) | GeeksforGeeks

You are given a one dimensional array that may contain both positive and negative integers, find the sum of contiguous subarray of numbers which has the largest sum.

Using Divide and Conquer approach, we can find the maximum subarray sum in O(nLogn) time. Following is the Divide and Conquer algorithm.

1) Divide the given array in two halves
2) Return the maximum of following three
….a) Maximum subarray sum in left half (Make a recursive call)
….b) Maximum subarray sum in right half (Make a recursive call)
….c) Maximum subarray sum such that the subarray crosses the midpoint

find the maximum sum starting from mid point and ending at some point on left of mid, then find the maximum sum starting from mid + 1 and ending with sum point on right of mid + 1. 

int maxCrossingSum(int arr[], int l, int m, int h)

{

    // Include elements on left of mid.

    int sum = 0;

    int left_sum = INT_MIN;

    for (int i = m; i >= l; i--)

    {

        sum = sum + arr[i];

        if (sum > left_sum)

          left_sum = sum;

    }

 

    // Include elements on right of mid

    sum = 0;

    int right_sum = INT_MIN;

    for (int i = m+1; i <= h; i++)

    {

        sum = sum + arr[i];

        if (sum > right_sum)

          right_sum = sum;

    }

 

    // Return sum of elements on left and right of mid

    return left_sum + right_sum;

}

 

// Returns sum of maxium sum subarray in aa[l..h]

int maxSubArraySum(int arr[], int l, int h)

{

   // Base Case: Only one element

   if (l == h)

     return arr[l];

 

   // Find middle point

   int m = (l + h)/2;

 

   /* Return maximum of following three possible cases

      a) Maximum subarray sum in left half

      b) Maximum subarray sum in right half

      c) Maximum subarray sum such that the subarray crosses the midpoint */

   return max(maxSubArraySum(arr, l, m),

              maxSubArraySum(arr, m+1, h),

              maxCrossingSum(arr, l, m, h));

}

Read full article from Divide and Conquer | Set 3 (Maximum Subarray Sum) | GeeksforGeeks