Maximum Subarray Sum using Divide and Conquer algorithm

Given an array arr[], the task is to find the subarray that has the maximum sum and return its sum.

Examples:

Input: arr[] = [2, 3, -8, 7, -1, 2, 3]
Output: 11
Explanation: The subarray [7, -1, 2, 3] has the largest sum 11.

Input: arr[] = [-2, -4]
Output: –2
Explanation: The subarray [-2] has the largest sum -2.

Input: arr[] = [5, 4, 1, 7, 8]
Output: 25
Explanation: The subarray [5, 4, 1, 7, 8] has the largest sum 25.

[Naive Approach] By iterating over all subarrays - O(n^2) Time and O(1) Space

The idea is to run two nested loops to iterate over all possible subarrays and find the maximum sum. The outer loop will mark the starting point of a subarray and inner loop will mark the ending point of the subarray. Please refer to Maximum Subarray Sum for implementation.

[Better Approach] Using Divide and Conquer - O(n*logn) time and O(n) space

Divide the given array in two halves and return the maximum of following three:

1. Maximum subarray sum in left half.
2. Maximum subarray sum in right half.
3. Maximum subarray sum such that the subarray crosses the midpoint.

Maximum subarray in left and right half can be found easily by two recursive calls. To find 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 some point on right of mid + 1. Finally, combine the two and return the maximum among left, right and combination of both.

Below is the implementation of the above approach: 

// C++ program for maximum subarray sum // using Divide and Conquer #include <bits/stdc++.h> using namespace std; // Find the maximum possible sum in arr[] such that arr[m] // is part of it int maxCrossingSum(vector<int> &arr, int l, int m, int h) {    // Include elements on left of mid.  int sum = 0;  int leftSum = INT_MIN;  for (int i = m; i >= l; i--) {  sum = sum + arr[i];  if (sum > leftSum)  leftSum = sum;  }  // Include elements on right of mid  sum = 0;  int rightSum = INT_MIN;  for (int i = m + 1; i <= h; i++) {  sum = sum + arr[i];  if (sum > rightSum)  rightSum = sum;  }  // Return the sum of maximum left, right, and   // cross subarray  return (leftSum + rightSum); } // Returns sum of maximum sum subarray in arr[l..h] int MaxSum(vector<int> &arr, int l, int h) {    // Invalid Range: low is greater than high  if (l > h)  return INT_MIN;  // Base Case: Only one element  if (l == h)  return arr[l];  // Find middle point  int m = l + (h - l) / 2;  // Compute the maximum of the three cases:  int leftSum = MaxSum(arr, l, m);  int rightSum = MaxSum(arr, m + 1, h);  int crossSum = maxCrossingSum(arr, l, m, h);  // Return the maximum of the three  if (leftSum >= rightSum && leftSum >= crossSum)  return leftSum;  else if (rightSum >= leftSum && rightSum >= crossSum)  return rightSum;  else  return crossSum; } int maxSubarraySum(vector<int> &arr) {  int n = arr.size();  return MaxSum(arr, 0, n - 1); } int main() {  vector<int> arr = {2, 3, 4, 5, 7};  cout << maxSubarraySum(arr);  return 0; } 

// Java program for maximum subarray sum // using Divide and Conquer import java.util.*; class GfG {    static int max(int a, int b) { return (a > b) ? a : b; }  static int max(int a, int b, int c) {  return max(max(a, b), c);  }  // Find the maximum possible sum in arr[] such that  // arr[m] is part of it  static int maxCrossingSum(int[] arr, int l, int m,  int h) {  // Include elements on left of mid  int sum = 0;  int leftSum = Integer.MIN_VALUE;  for (int i = m; i >= l; i--) {  sum += arr[i];  if (sum > leftSum)  leftSum = sum;  }  // Include elements on right of mid  sum = 0;  int rightSum = Integer.MIN_VALUE;  for (int i = m; i <= h; i++) {  sum += arr[i];  if (sum > rightSum)  rightSum = sum;  }  // Return maximum of left sum, right sum, and their  // combination  return max(leftSum + rightSum - arr[m], leftSum,  rightSum);  }  // Recursive function to calculate maximum subarray sum  static int MaxSum(int[] arr, int l,  int h) {  // Invalid range  if (l > h)  return Integer.MIN_VALUE;  // Base case: one element  if (l == h)  return arr[l];  // Find middle point  int m = l + (h - l) / 2;  // Return the maximum of three cases:  // 1. Maximum subarray sum in left half  // 2. Maximum subarray sum in right half  // 3. Maximum subarray sum crossing the midpoint  return max(MaxSum(arr, l, m),  MaxSum(arr, m + 1, h),  maxCrossingSum(arr, l, m, h));  }  static int maxSubarraySum(int[] arr) {  return MaxSum(arr, 0, arr.length - 1);  }  public static void main(String[] args) {  int[] arr = { 2, 3, 4, 5, 7 };  System.out.println(maxSubarraySum(arr));  } } 

# Python program for maximum subarray sum # using Divide and Conquer def max(a, b, c=None): if c is None: return a if a > b else b return max(max(a, b), c) def maxCrossingSum(arr, l, m, h): # Include elements on the left of mid leftSum = float('-inf') sum = 0 for i in range(m, l - 1, -1): sum += arr[i] leftSum = max(leftSum, sum) # Include elements on the right of mid rightSum = float('-inf') sum = 0 for i in range(m, h + 1): sum += arr[i] rightSum = max(rightSum, sum) # Return the maximum of left sum, right sum, and their combination return max(leftSum + rightSum - arr[m], leftSum, rightSum) def MaxSum(arr, l, h): if l > h: return float('-inf') if l == h: # Base case: one element return arr[l] # Find the middle point m = l + (h - l) // 2 # Return the maximum of three cases return max( MaxSum(arr, l, m), MaxSum(arr, m + 1, h), maxCrossingSum(arr, l, m, h), ) def maxSubarraySum(arr): return MaxSum(arr, 0, len(arr) - 1) arr = [2, 3, 4, 5, 7] print(maxSubarraySum(arr)) 

// C# program for maximum subarray sum // using Divide and Conquer using System; class GfG {  static int max(int a, int b) { return (a > b) ? a : b; }  static int max(int a, int b, int c) {  return max(max(a, b), c);  }  // Function to calculate the maximum crossing subarray  // sum  static int maxCrossingSum(int[] arr, int l, int m,  int h) {  int sum = 0;  // Calculate maximum sum on the left side of the  // midpoint  int leftSum = int.MinValue;  for (int i = m; i >= l; i--) {  sum += arr[i];  leftSum = Math.Max(leftSum, sum);  }  // Calculate maximum sum on the right side of the  // midpoint  sum = 0;  int rightSum = int.MinValue;  for (int i = m; i <= h; i++) {  sum += arr[i];  rightSum = Math.Max(rightSum, sum);  }  // Return the maximum combined sum, or either left  // or right sum  return max(leftSum + rightSum - arr[m], leftSum,  rightSum);  }  static int MaxSum(int[] arr, int l,  int h) {  // Base case: invalid range  if (l > h)  return int.MinValue;  // Base case: single element  if (l == h)  return arr[l];  int m = l + (h - l) / 2;  return max(MaxSum(arr, l, m),  MaxSum(arr, m + 1, h),  maxCrossingSum(arr, l, m, h));  }  static int maxSubarraySum(int[] arr) {  return MaxSum(arr, 0, arr.Length - 1);  }  static void Main(string[] args) {  int[] arr = { 2, 3, 4, 5, 7 };  Console.WriteLine(maxSubarraySum(arr));  } } 

// JavaScript program for maximum subarray sum // using Divide and Conquer function max(a, b, c = null) {  if (c === null)  return a > b ? a : b;  return Math.max(a, Math.max(b, c)); } function maxCrossingSum(arr, l, m, h) {  let leftSum = -Infinity, sum = 0;  // Calculate maximum sum on the left side of the  // midpoint  for (let i = m; i >= l; i--) {  sum += arr[i];  leftSum = Math.max(leftSum, sum);  }  let rightSum = -Infinity;  sum = 0;  // Calculate maximum sum on the right side of the  // midpoint  for (let i = m; i <= h; i++) {  sum += arr[i];  rightSum = Math.max(rightSum, sum);  }  // Return the maximum combined sum, or either left or  // right sum  return max(leftSum + rightSum - arr[m], leftSum,  rightSum); } function MaxSum(arr, l, h) {  // Base case: invalid range  if (l > h)  return -Infinity;  // Base case: single element  if (l === h)  return arr[l];  const m = l + Math.floor((h - l) / 2);  return max(MaxSum(arr, l, m),  MaxSum(arr, m + 1, h),  maxCrossingSum(arr, l, m, h)); } function maxSubarraySum(arr) {  return MaxSum(arr, 0, arr.length - 1); } //driver code const arr = [ 2, 3, 4, 5, 7 ]; console.log(maxSubarraySum(arr)); 

21

Note: The above recurrence is similar to Merge Sort and can be solved either using Recurrence Tree method or Master method.

[Expected Approach] Using Kadane’s Algorithm - O(n) Time and O(1) Space

The Kadane's Algorithm for this problem takes O(n) time. Therefore the Kadane's algorithm is better than the Divide and Conquer approach, but this problem can be considered as a good example to show power of Divide and Conquer. The above simple approach where we divide the array in two halves, reduces the time complexity from O(n^2) to O(nLogn). Please refre to kadane's algorithm implementation Maximum Subarray Sum.