Recursion - Data Structures and Problem Solving Using Java - page 323

The general form for the recursive call is to pass the input array along
with the left and right borders, which delimit the portion of the array being
operated on. A one-line driver routine sets this action up by passing the bor-
ders 0 and N - 1 along with the array.
Lines 12 and 13 handle the base case. If left==right , there is one element,
and it is the maximum contiguous subsequence if the element is nonnegative
(otherwise, the empty sequence with sum 0 is maximum). Lines 15 and 16
perform the two recursive calls. These calls are always on a smaller problem
than the original; thus we progress toward the base case. Lines 18 to 23 and
then 25 to 30 calculate the maximum sums that touch the center border. The
sum of these two values is the maximum sum that spans both halves. The rou-
tine max3 (not shown) returns the largest of the three possibilities.

7.5.2 analysis of a basic
divide-and-conquer recurrence

The recursive maximum contiguous subsequence sum algorithm works by
performing linear work to compute a sum that spans the center border and
then performing two recursive calls. These calls collectively compute a sum
that spans the center border, do further recursive calls, and so on. The total
work performed by the algorithm is then proportional to the scanning done
over all the recursive calls.
Figure 7.21 graphically illustrates how the algorithm works for N = 8 ele-
ments. Each rectangle represents a call to maxSumRec , and the length of the rect-
angle is proportional to the size of the subarray (and hence the cost of the
scanning of the subarray) being operated on by the invocation. The initial call
is shown on the first line: The size of the subarray is N, which represents the
cost of the scanning for the third case. The initial call then makes two recur-
sive calls, yielding two subarrays of size N / 2. The cost of each scan in case 3
is half the original cost, but as there are two such recursive calls, the com-
bined cost of these recursive calls is also N . Each of those two recursive
instances themselves make two recursive calls, yielding four subproblems that
are a quarter of the original size. Thus the total of all case 3 costs is also N .
Eventually, we reach the base case. Each base case has size 1, and there
are N of them. Of course, there are no case 3 costs in this instance, but we
charge 1 unit for performing the check that determines whether the sole ele-
ment is positive or negative. The total cost then, as illustrated in Figure 7.21,
is N per level of recursion. Each level halves the size of the basic problem, so
the halving principle tells us that there are approximately log N levels. In fact,
the number of levels is 1 + ⎡ log N ⎤ (which is 4 when N equals 8). Thus we
expect that the total running time is O ( N log N ).

Intuitive analysis of
the maximum
contiguous subse-
quence sum
divide-and-conquer
algorithm: We
spend O ( N ) per
level.