The Maximum Subarray Problem: Suppose you are given an array of n integers. The integers may contain negative numbers. We want to find a (contiguous) subarray whose numbers sum to the most possible. For example, if A= (−5,−6,3,−2,7,−6,2,1), then the maximum subarray would be(3,−2,7)because it sums to 8 and there is no other subarray that sums that high. Solve the problem using divide and conquer, in time O(nlogn).
Brutal force will consider all possible subarrays, there are $n^2$ subarrays, so the total time is $O(n^2)$ time.
There are three possible ways of locating the ideal (i,j) for the max array:
in left half
in right half
in the region that cross the middle
The third case is not a recursion process. All three cases return the max array for that part.(Correctness).
The termination should be when high == low, return (low, high, A[low ])
After returning three cases, we should do comparison between them.