Analysis of “Finding Maximum Sum of Subsequent Elements” algorithm

Question

If possible, I would like someone to give an analytic explanation of the algorithm.

For example, given the sequence

-2, 4, -1, 3, 5, -6, 1, 2 

the maximum subsequence sum would be

4 + -1 + 3 + 5 = 11

This algorithm I am reffering to is an divide and cconquer type algorithm.

The algorithm is O(nlogn) complexity.

Actually i seek to see an example of all the steps that this algorithm produces. The above sequence could be used for the example.

Answer 1

The idea is to split your sequence in half, find the answers for both halves, then use that to find the answer for the entire sequence.

Assume you have a sequence [left, right]. Let m = (left + right) / 2. Now, the maximum sum subsequence (MSS) of [left, right] is either MSS(left, m), MSS(m + 1, right) or a sequence that starts in [left, m] and ends somewhere in [m + 1, right].

Pseudocode:

MSS(left, right)
  if left = right then return sequence[left]
  m = (left + right) / 2
  leftMSS = MSS(left, m)
  rightMSS = MSS(m + 1, right)

  maxLeft = -inf // find the maximum sum subsequence that ends with m and starts with at least left
  cur = 0
  i = m
  while i >= left do
    cur += sequence[i]
    if cur > maxLeft
      maxLeft = cur

  maxRight = -inf // find the maximum sum subsequence that starts with m + 1 and ends with at most right
  cur = 0
  i = m + 1
  while i <= right
    cur += sequence[i]
    if cur > maxRight
      maxRight = cur

  return max(leftMSS, rightMSS, maxLeft + maxRight)

This is O(n log n) because the recursion three has height O(log n) and at each level of the tree we do O(n) work.

Here is how it would run on -2, 4, -1, 3, 5, -6, 1, 2:

 0  1  2 3 4  5 6 7
-2  4 -1 3 5 -6 1 2

                                             MSS(0, 7) = 11
                                      /                    \
                              MSS(0, 3) = 6                 MSS(4, 7) = 5 ------
                          /                  \              |                   \
           MSS(0, 1) = 4                    MSS(2, 3) = 3   MSS(4, 5) = 5      NSS(6, 7) = 3
             /       \                    /              \
   MSS(0, 0) = -2     MSS(1, 1) = 4    MSS(2, 2) = -1    MSS(3, 3) = 3

Of interest is the computation of MSS(0, 3) and MSS(0, 7), since these do not simply take the max of their children. For MSS(0, 3) we try to make as large a sum as possible adding consecutive elements starting with the middle of the interval (1) and going left. This max is 4. Next we do the same starting with the middle of the interval + 1 and going right. This max is 2. Adding these together gets us a maximum sum subsequence with the sum of 6, which is larger than the maximum sum subsequence of the two child intervals, so we take this one instead.

The reasoning is similar for MSS(0, 7).

Answer 2

This can actually be done in O(n) time using an algorithm called Kadane's algorithm. I have written up my own version and an analysis of its complexity if you're interested. The idea is to use dynamic programming to incrementally improve a solution until an optimal subsequence can be found.