Revisiting Max Subarray Problem

Sometime back I discussed and solved a problem to find out a subarray from an array which has the maximum sum- here.

I solved the problem using brute force, that is, all the sub arrays were actually created and maximum sum subarray was found. That solution was created in order of N^2 complexity.

Let’s see how can we improve on our solution using divide and conquer approach.

Array: {-1,2,4,60,1,3,-2,-6,7,-9}

If we divide the original array into two half arrays from mid of the array. one of the following must be true

1. Max Subarray is part of first half {-1,2,4,60,1}

2. Max Sub array is part of second half {3,2,-6,7,-9}

3. Max Subarray passes through the mid of array

Array with maximum sum and passes through mid can be easily figured out in order of N. In this we will simply keep moving left and right from the mid until we hit maximum sum array, so first subarray would be 2+4+60+1+3=70

To solve 1 and 2 we will recursively use the approach with the 2 sub arrays (Repeatedly divide the array and find max having mid of the array).

The problem set is getting reduced to half with every iteration, so Log N iterations will be there in total. At max N elements are added (compared to be -ve), in each iteration, hence the total complexity of the algorithm is (N log N), so we are able to reduce the complexity from N^2 to (N log N) with the help of divide and conquer approach.