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

problem, the solution here is thematic of others in a wide range of applica-
tions, including the sorting algorithms, such as mergesort and quicksort,
discussed in Chapter 8. Consequently, learning the technique is important.
Finally, we show the general form for the running time of a broad class of
divide-and-conquer algorithms.

7.5.1 the maximum contiguous
subsequence sum problem

In Section 5.3 we discussed the problem of finding, in a sequence of numbers,
a contiguous subsequence of maximum sum. For convenience, we restate the
problem here.

maximum contiguous subsequence sum problem
Given (possibly negative) integers , find (and identify the sequence
corresponding to) the maximum value of . The maximum contiguous sub-
sequence sum is zero if all the integers are negative.

A 1 A 2 , , … A N ,

j

∑

A k

ki =

We presented three algorithms of various complexity. One was a cubic
algorithm based on an exhaustive search: We calculated the sum of each pos-
sible subsequence and selected the maximum. We described a quadratic
improvement that takes advantage of the fact that each new subsequence can
be computed in constant time from a previous subsequence. Because we have
O ( N 2 ) subsequences, this bound is the best that can be achieved with an
approach that directly examines all subsequences. We also gave a linear-time
algorithm that works by examining only a few subsequences. However, its
correctness is not obvious.
Let us consider a divide-and-conquer algorithm. Suppose that the sample
input is {4, -3, 5, -2, -1, 2, 6, -2}. We divide this input into two halves, as
shown in Figure 7.19. Then the maximum contiguous subsequence sum can
occur in one of three ways.

The maximum con-
tiguous subse-
quence sum prob-
lem can be solved
with a divide-and-
conquer algorithm.

Case 1: It resides entirely in the first half.

n

Case 2: It resides entirely in the second half.

n

Case 3: It begins in the first half but ends in the second half.

n

We show how to find the maximums for each of these three cases more effi-
ciently than by using an exhaustive search.
We begin by looking at case 3. We want to avoid the nested loop that
results from considering all N / 2 starting points and N / 2 ending points inde-
pendently. We can do so by replacing two nested loops by two consecutive
loops. The consecutive loops, each of size N / 2, combine to require only linear