Objective: The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum.
Example:
int [] A = {−2, 1, −3, 4, −1, 2, 1, −5, 4};
Output: contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.
Approach:
Earlier we have seen how to solve this problem using Kadane’s Algorithm and using Dynamic programming. In this article we will solve the problem using divide and conquer.
1. Task is to find out subarray which has the largest sum. So we need to find out the 2 indexes (left index and right index) between which the sum is maximum.
2. Divide the problem into 2 parts, left half and right half.
- Now we can conclude the final result will be in one of the three possibilities.
- Left half of the array. (Left index and right index both are in left half of the array).
- Right half of the array. (Left index and right index both are in right half of the array).
- Result will cross the middle of the array. (Left index in the and left half of the array and right index in right half of the array).
- Solve the all three and return the maximum among them.
- Left half and right half of the array will be solved recursively.
Complete Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class MaximumSubArray { | |
| public int maxSubArray(int [] A){ | |
| if(A.length==0)//if length = 0, return 0 | |
| return 0; | |
| else | |
| return maxSubArray(A, 0, A.length–1); | |
| } | |
| public int maxSubArray(int [] A, int start, int end){ | |
| if(start==end){ | |
| return A[start]; //if only one element, return that | |
| } | |
| int mid = start + (end–start)/2; | |
| int leftMaxSum = maxSubArray(A, start, mid); | |
| int rightMaxSum = maxSubArray(A, mid+1, end); | |
| //lets calculate the part in which sub array will start in the left half and ends in right half | |
| int sum = 0; | |
| int leftMidMax =0; | |
| for (int i = mid; i >=start ; i—) { | |
| sum += A[i]; | |
| if(sum>leftMidMax) | |
| leftMidMax = sum; | |
| } | |
| sum = 0; | |
| int rightMidMax =0; | |
| for (int i = mid+1; i <=end ; i++) { | |
| sum += A[i]; | |
| if(sum>rightMidMax) | |
| rightMidMax = sum; | |
| } | |
| int centerSum = leftMidMax + rightMidMax; | |
| return Math.max(centerSum, Math.max(leftMaxSum, rightMaxSum)); | |
| } | |
| public static void main(String[] args) { | |
| int [] A = {–2, 12, –5, 10, –1, –6, 4}; | |
| MaximumSubArray m = new MaximumSubArray(); | |
| System.out.println("Maximum Sub Array sum is : " + m.maxSubArray(A)); | |
| } | |
| } |
Output:
Maximum Sub Array sum is : 17