Understanding Recursion / how are subproblems combined (Max-Subarray Algorithm)

Question

I'm having some problems understanding divide and conquer algorithms. I've read that in order to apply recursion successfully you need to have a "recursive leap of faith" and you shouldn't bother with the details of every step, but I'm not really satisfied with just accepting that recursion works if all the conditions are fulfilled, because it seems like magic to me at the moment and I want to understand why it works.

So I'm given the following recursive algorithm of finding a maximum subarray in pseudocode:

Find-Maximum-Subarray(A, low, high)
if high == low
    return (low, high, A[low])
else
    mid = [(low + high)/2]
    (left-low, left-high, left-sum) = Find-Maximum-Subarray(A, low, mid)
    (right-low, right-high, right-sum) = Find-Maximum-Subarray(A,mid + 1, high)
    (cross-low, cross-high, cross-sum) = Find-Max-Crossing-Subarray(A,low, mid, high)
    if left-sum >= right-sum and left-sum >= cross-sum
        return (left-low, left-high, left-sum)
    else if right-sum >= left-sum and right-sum >= cross-sum
        return (right-low, right-high, right-sum)
    else
        return (cross-low, cross-high, cross-sum)

where the Find-Max-Crossing-Subarray algorithm is given by the following pseudocode:

Find-Maximum-Crossing-Subarray(A, low, mid, high)
left-sum = -INF
sum = 0
for i = mid down to low
    sum = sum + A[i]
    if sum > left-sum
        left-sum = sum
        max-left = i
right-sum = -INF
sum = 0
for j = mid + 1 to high
    sum = sum + A[j]
    if sum > right-sum 
        right-sum = sum
        max-right = j
return (max-left, max-right, left-sum + right-sum)

Now when I try to apply this algorithm to an example, I'm having a hard time understanding all the steps.

The array is "broken down" (using the indices, without actually changing the array itself) until high equals low. I thinks this corresponds to the first call, so Find-Maximum-Subarray is first called for all the terms on the left of the array, until high==low==1. Then (low, high, A[low]) is returned which would be (1, 1, A[1]) in this case. Now I don't understand how those values are processed in the remainder of the call.

Furthermore I don't understand how the algorithm actually compares subarrays of lengths > 1. Can anybody explain to me how the algorithm continues once one of the calls of the function has bottomed out, please?

Answer 1

In short:
Let A be an array of length n. You want to compute the max subarray of A sou you call Find-Maximum-Subarray(A, 0, n-1). Now try to make the problem easier:

1. Case. high = low:
   In this case the Array has only 1 Element so the solution is simple

2. high != low
   In this case the solutions are to hard to find. so try to make the problem smaller. What happens if we cut the array A into arrays B1 and B2 of the half length. Now there are only 3 new cases

   a) the Max Subarray of A is also a subarray of B1 but not of B2
   b) The max subarray of A is also a subarray of B2 but not of B1
   c) The max subarray of A overlaps with B1 and B2

   so you compute the max subarray of B1 and B2 separately and look for an overlapping solution and finally you take the largest one.

The trick is now, that you can du the same thing with B1 and B2.

Example:

A =[-1, 2, -1, 1]
Call Find-Maximum-Subarray(A, 0, 3);
 - Call Find-Maximum-Subarray(A, 0, 1); -> returns ( 1, 1, 2 )  (cause 2 > 1 > -1,  see the subcalls)
    - Call Find-Maximum-Subarray(A, 0, 0); -> returns ( 0, 0, -1 )
    - Call Find-Maximum-Subarray(A, 1, 1); -> returns ( 1, 1, 2 )
    - Call Find-Max-Crossing-Subarray(A, 0, 0, 1); -> returns ( 0, 1, 1 )
 - Call Find-Maximum-Subarray(A, 2, 3); -> returns ( 3, 3, 1 ) ( 1 > 0 > -1, see subcalls)
    - Call Find-Maximum-Subarray(A, 2, 2); -> returns ( 2, 2, -1 )
    - Call Find-Maximum-Subarray(A, 3, 3); -> returns ( 3, 3, 1 )
    - Call Find-Max-Crossing-Subarray(A, 2, 2, 3); returns ( 2, 3, 0 )
 - Call Find-Max-Crossing-Subarray(A, 0, 1, 3); -> returns ( 1, 3, 2 )
    - Here you have to take at least the elements A[1] and A[2] with the sum of 1, 
      but if you also take A[3]=1 the sum will be 2. taking A[0] does not help 
      due to A[0] is negative
 - Now you have only to look which subarray has the larger sum. In this case you 
   have two with the same size: A[1] and A[1-3]. Return one of them.