Data Structures, Algorithms, & Applications in C++
Chapter 19, Exercise 23

First let use try the divide-and-conquer method. We use the term block to denote a consecutive subset of the xis. For example, xj, xj+1, ..., xk, denotes a block.

If n = 1, there is only one block. This block is the block with maximum sum. If n > 1, divide the elements into two groups; one group has ceil(n/2) elements and the other has the remaining elements. For each group, find the block with maximum sum recursively. The block with overall maximum sum is either one of these two blocks or is a block that spans the two groups. The maximum sum block that spans the two groups is comprised of two parts: a max subblock that ends at the right end of the left group and a max subblock that begins at the left of the right subgroup. Suppose that the left group ends at xq. The max subblock that ends at xq can be found in linear time by computing the sums s(i) = xi + xi+1 + ... + xq for i = 0, 1, 2, ..., q, and then taking the max of these sums. The max subblock that begins at xq+1 can be found similarly. The two max sublocks are combined to get the max subblock that spans the two groups.

To make the analysis easy, assume that n is a power of 2. Let t(n) denote the time complexity. We see that t(n) = 2t(n/2)+cn when n >= 2. This is the same equation as for merge sort. Therefore, t(n) = O(n log n).

Next consider a dynamic programming formulation. Let s(i) be the maximum sum of any block of xi, xi+1, ..., xn. We see that s(1) = max{sum(i,j)}.

First we make the following observations
  1. s(n) = xn.
  2. For i < n, s(i) is either the sum of a block that begins with xi (i.e., s(i) = sum(i,j) for some j >= i), or it is the sum of a block that does not include xi (i.e., s(i) = s(i+1)).


These observations lead to the following dynamic programming recurrence:
(1) s(n) = xn
(2) s(i) = max{maxSum(i), s(i+1)}
where maxSum(i) = max{sum(i,j) | j >= i}. Equations (1) and (2) yield
(3) s(1) = max{maxSum(i)}

For maxSum(i) make the following observations:
  1. maxSum(n) = xn
  2. Let i < n. maxSum(i) = xi whenever maxSum(i+1) <= 0 and maxSum(i) = xi + maxSum(i+1) otherwise.
These observations result in the following dynamic programming recurrence for maxSum:
(4) maxSum(n) = xn
(5) maxSum(i) = max{xi, xi + maxSum(i+1)}, i < n

We may determine the block with maximum sum as follows:
Step 1
Set maxSum(n) = xn.
This takes O(1) time.
Step 2
Compute maxSum(i) for i = n-1, n-2, ..., 1, in that order, using Equation (5).
This takes O(n) time.

Step 3
Use Equation (3) to compute s(1).
This takes O(n) time.

Step 4
The block whose sum equals s(1) is determined in the following way. Let k be such that s(1) = maxSum(k). The block with maximum sum begins at xk. To find the block end, find the least j >= i such that sum(k,j) = maxSum(k).
The time required for this is O(n).


From the above description and analysis, we see that the overall complexity is O(n).