Maximum sub array problem

Maximum sub array problem:

The maximum sub array problem is the task of finding the contiguous sub array within a one dimensional array, a[1...n], of numbers which has the largest sum, where, the list usually contains both positive and negative numbers along with 0.

Using Divide and Conquer approach, we can find the maximum sub array sum in O(nlogn) time.

A solution using divide-and-conquer:

To find a maximum subarray of the subarray A[low..high]. Divide-and-conquer suggests that we divide the subarray into two subarrays of as equal size as possible.

Any contiguous subarray A[i..j] of A[low .. high] must lie in exactly one of the following places:

• entirely in the subarray A[low .. mid], so that low <= i<= j <= mid,

• entirely in the subarray A[mid +1.. high], so that mid < i <= j <= high, or

• crossing the midpoint, so that low <= i <= mid < j <= high.

Therefore, a maximum subarray of A[low .. high] must lie in exactly one of these places.
We can find maximum subarrays of A[low .. mid] and A[mid+1 .. high] recursively. Thus, all that is left to do is find a maximum subarray that crosses the midpoint, and take a subarray with the largest sum of the three.

Example:

Pseudocode for a divide-and-conquer algorithm to solve the maximum subarray problem:

The procedure FIND-MAX-CROSSING-SUBARRAY takes as input the array A and the indices low, mid, and high, and it returns a tuple containing the indices delimit a maximum subarray that crosses the midpoint, along with the sum of the values in a maximum subarray.

Analyzing the divide-and-conquer algorithm

We denote by T(n) the running time of FIND-MAXIMUM-SUBARRAY on a subarray of n elements. 

The base case, when n=1, is easy: line 2 takes constant time, and so 

The recursive case occurs when n > 1. Lines 1 and 3 take constant time. 

Each of the subproblems solved in lines 4 and 5 is on a subarray of n/2 elements, and so we spend T(n/2) time solving each of them. Because we have to solve two subproblems—for the left subarray and for the right subarray—the contribution to the running time from lines 4 and 5 comes to 2T(n/2).

For the recursive case, therefore, we have

Combining equations gives us a recurrence for the running time T(n) of FIND-MAXIMUM-SUBARRAY:

this recurrence has the solutionT (n)=θ(n lg n).

Thus, we see that the divide-and-conquer method yields an algorithm that is asymptotically faster than the brute-force method which takes Ω(n²).