Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Maximum Subarray OR Largest Sum Contiguous Subarray Problem – Divide and Conquer

Objec­tive:  The max­i­mum sub­ar­ray prob­lem is the task of find­ing the con­tigu­ous sub­ar­ray within a one-dimensional array of num­bers which has the largest sum.

Exam­ple:

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:

Ear­lier we have seen how to solve this prob­lem using Kadane’s Algo­rithm and using Dynamic pro­gram­ming. In this arti­cle we will solve the prob­lem using divide and conquer.

1.     Task is to find out sub­ar­ray 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 prob­lem into 2 parts, left half and right half.

  1. Now we can con­clude the final result will be in one of the three possibilities.
    1. Left half of the array. (Left index and right index both are in left half of the array).
    2. Right half of the array. (Left index and right index both are in right half of the array).
    3. Result will cross the mid­dle of the array. (Left index in the and left half of the array and right index in right half of the array).
  2. Solve the all three and return the max­i­mum among them.
  3. Left half and right half of the array will be solved recursively.

Com­plete Code:

Out­put:

Maximum Sub Array sum is : 17

You may also like...