Given an array of integers, find maximum sum subarray among all subarrays possible.
For example,
Input: A[]= [2, -4, 1, 9, -6, 7, -3]
Output:The maximum sum of the subarray is 11 (Marked in Green)
Naive solution would be to consider every possible subarray and find sum of all of them and take maximum. The problem with this approach is that its worst case time complexity is O(n2).
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <stdio.h> #include <limits.h> // Naive solution to find maximum sum subarray using // divide and conquer int maximum_sum(int A[], int n) { int max_sum = INT_MIN; int sum = 0; // do for each subarray starting with i for (int i = 0; i < n - 1; i++) { // calculate sum of subarray A[i..j] sum = 0; // reset sum // do for each subarray ending with j for (int j = i; j < n; j++) { sum += A[j]; // if current subarray sum is greater than the maximum // sum calculated so far, update the maximum sum if (sum > max_sum) max_sum = sum; } } return max_sum; } // Maximum Sum Subarray using Divide & Conquer int main(void) { int arr[] = { 2, -4, 1, 9, -6, 7, -3 }; int n = sizeof(arr) / sizeof(arr[0]); printf("The maximum sum of the subarray is %d", maximum_sum(arr, n)); return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
class MaximumSum { // Naive solution to find Maximum sum subarray using // divide and conquer public static int MaximumSum(int[] A) { int maxSum = Integer.MIN_VALUE; int sum = 0; // do for each subarray starting with i for (int i = 0; i < A.length - 1; i++) { // calculate sum of subarray A[i..j] sum = 0; // reset sum // do for each subarray ending with j for (int j = i; j < A.length; j++) { sum += A[j]; // if current subarray sum is greater than the maximum // sum calculated so far, update the maximum sum if (sum > maxSum) { maxSum = sum; } } } return maxSum; } public static void main(String[] args) { int[] A = { 2, -4, 1, 9, -6, 7, -3 }; System.out.println("The Maximum sum of the subarray is " + MaximumSum(A)); } } |
Output:
The maximum sum of the subarray is 11
How can we perform better?
The idea is to use divide and conquer to find the maximum subarray sum. The algorithm works as follows –
- Divide the array into two equal subarrays.
- Recursively calculate the maximum subarray sum for left subarray.
- Recursively calculate the maximum subarray sum for right subarray.
- Find the maximum subarray sum that crosses mid element.
- Return the maximum of above three sums.
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <stdio.h> #include <limits.h> // Utility function to find maximum of two numbers int max(int x, int y) { return (x > y) ? x : y; } // Function to find maximum subarray sum using divide and conquer int maximum_sum(int A[], int low, int high) { // If array contains only one element if (high == low) return A[low]; // Find middle element of the array int mid = (low + high) / 2; // Find maximum subarray sum for the left subarray // including the middle element int left_max = INT_MIN; int sum = 0; for (int i = mid; i >= low; i--) { sum += A[i]; if (sum > left_max) left_max = sum; } // Find maximum subarray sum for the right subarray // excluding the middle element int right_max = INT_MIN; sum = 0; // reset sum to 0 for (int i = mid + 1; i <= high; i++) { sum += A[i]; if (sum > right_max) right_max = sum; } // Recursively find the maximum subarray sum for left subarray // and right subarray and take maximum int max_left_right = max(maximum_sum(A, low, mid), maximum_sum(A, mid + 1, high)); // return maximum of the three return max(max_left_right, left_max + right_max); } // Maximum Sum Subarray using Divide & Conquer int main(void) { int arr[] = { 2, -4, 1, 9, -6, 7, -3 }; int n = sizeof(arr) / sizeof(arr[0]); printf("The maximum sum of the subarray is %d", maximum_sum(arr, 0, n - 1)); return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
class MaximumSum { // Function to find Maximum subarray sum using // divide and conquer public static int MaximumSum(int[] A, int left, int right) { // If array contains only one element if (right == left) { return A[left]; } // Find middle element of the array int mid = (left + right) / 2; // Find maximum subarray sum for the left subarray // including the middle element int leftMax = Integer.MIN_VALUE; int sum = 0; for (int i = mid; i >= left; i--) { sum += A[i]; if (sum > leftMax) { leftMax = sum; } } // Find maximum subarray sum for the right subarray // excluding the middle element int rightMax = Integer.MIN_VALUE; sum = 0; // reset sum to 0 for (int i = mid + 1; i <= right; i++) { sum += A[i]; if (sum > rightMax) { rightMax = sum; } } // Recursively find the maximum subarray sum for left // subarray and right subarray and tale maximum int maxLeftRight = Integer.max(MaximumSum(A, left, mid), MaximumSum(A, mid + 1, right)); // return maximum of the three return Integer.max(maxLeftRight, leftMax + rightMax); } public static void main(String[] args) { int[] A = { 2, -4, 1, 9, -6, 7, -3 }; System.out.println("The Maximum sum of the subarray is " + MaximumSum(A, 0, A.length - 1)); } } |
Output:
The maximum sum of the subarray is 11
Maximum Sum Subarray Solution Performance –
The time complexity of above D&C solution is O(nlogn) as for given array of size n, we make two recursive calls on input size n/2 and finding maximum subarray that crosses midpoint takes O(n) time in worst case. So,
T(n) = 2T(n/2) + O(n)
T(n) = O(nlogn)
We can also solve this problem in O(n) time using Kadane’s algorithm.
(1 votes, average: 5.00 out of 5)
Loading...
Thanks for reading.
Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply