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

work. We can make this substitution because any contiguous subsequence that
begins in the first half and ends in the second half must include both the last
element of the first half and the first element of the second half.
Figure 7.19 shows that for each element in the first half, we can calculate
the contiguous subsequence sum that ends at the rightmost item. We do so
with a right-to-left scan, starting from the border between the two halves.
Similarly, we can calculate the contiguous subsequence sum for all sequences
that begin with the first element in the second half. We can then combine these
two subsequences to form the maximum contiguous subsequence that spans
the dividing border. In this example, the resulting sequence spans from the
first element in the first half to the next-to-last element in the second half. The
total sum is the sum of the two subsequences, or 4 + 7 = 11.
This analysis shows that case 3 can be solved in linear time. But what
about cases 1 and 2? Because there are N / 2 elements in each half, an
exhaustive search applied to each half still requires quadratic time per half;
specifically, all we have done is eliminate roughly half of the work, and half
of quadratic is still quadratic. In cases 1 and 2 we can apply the same strat-
egy—that of dividing into more halves. We can keep dividing those quarters
further and further until splitting is impossible. This approach is succinctly
stated as follows: Solve cases 1 and 2 recursively. As we demonstrate later,
doing so lowers the running time below quadratic because the savings com-
pound throughout the algorithm. The following is a summary of the main por-
tion of the algorithm:

1. Recursively compute the maximum contiguous subsequence sum that

resides entirely in the first half

2. Recursively compute the maximum contiguous subsequence sum that

resides entirely in the second half

3. Compute, via two consecutive loops, the maximum contiguous subse-

quence sum that begins in the first half but ends in the second half

4. Choose the largest of the three sums.

figure 7.19
Dividing the maximum
contiguous
subsequence problem
into halves

First Half Second Half

4 -3 5 -2 -1 2 6 -2 Values

0

4* 3 -2 -1 1 7* 5

Running sums

Running sum from the center (*denotes
maximum for each half).