MaxSubarray(A,low,high) // if high == low return (low, high, A[low]) // base cas

ID: 3773687 • Letter: M

Question

MaxSubarray(A,low,high)
//
if high == low
   return (low, high, A[low]) // base case: only one element
else
   // divide and conquer
   mid = floor( (low + high)/2 )
   (leftlow,lefthigh,leftsum) = MaxSubarray(A,low,mid)
   (rightlow,righthigh,rightsum) = MaxSubarray(A,mid+1,high)
   (xlow,xhigh,xsum) = MaxXingSubarray(A,low,mid,high)
   // combine
   if leftsum >= rightsum and leftsum >= xsum
      return (leftlow,lefthigh,leftsum)
   else if rightsum >= leftsum and rightsum >= xsum
      return (rightlow,righthigh,rightsum)
   else
      return (xlow,xhigh,xsum)
   end if
end if

--------------------------------------------------------------

MaxXingSubarray(A,low,mid,high)
// Find a max-subarray of A[i..mid]
leftsum = -infty
sum = 0
for i = mid downto low
    sum = sum + A[i]
    if sum > leftsum
       leftsum = sum
       maxleft = i
    end if
end for
// Find a max-subarray of A[mid+1..j]
rightsum = -infty
sum = 0
for j = mid+1 to high
    sum = sum + A[j]
    if sum > rightsum
       rightsum = sum
       maxright = j
    end if
end for
// Return the indices i and j and the sum of the two subarrays
return (maxleft,maxright,leftsum + rightsum)

-----------------------------------------------------------

=== Remarks:

(1) Initial call: MaxSubarray(A,1,n)

(2) Divide by computing mid.
    Conquer by the two recursive alls to MaxSubarray.
    Combine by calling MaxXingSubarray and then determining
       which of the three results gives the maximum sum.

(3) Base case is when the subarray has only 1 element.

Explanation / Answer

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:

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.

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:

Case. high = low:
In this case the Array has only 1 Element so the solution is simple
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