Be the first user to complete this post

Add to List 
Maximum Subarray OR Largest Sum Contiguous Subarray Problem – Divide and Conquer
Objective: The maximum subarray problem is the task of finding the contiguous subarray within a onedimensional 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 the 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, the left half and the right half.
 Now we can conclude the final result will be in one of the three possibilities.
 The left half of the array. (Left index and right index both are in the left half of the array).
 The right half of the array. (Left index and right index both are in the right half of the array).
 The result will cross the middle of the array. (Left index in the left half of the array and right index in the right half of the array).
 Solve all three and return the maximum among them.
 The left half and right half of the array will be solved recursively.
Code:
Output:
Maximum Sub Array sum is : 17
Also Read: