MVCS using Divide and Conquer

Question

Recall the Maximum Value Contiguous Subsequence problem that we studied in class: “Given an Array A(1..n) of positive and negative values, find a contiguous subsequence A(i..j) such that the sum of the terms in the subarray is maximized”.  We studied a linear time O(n) dynamic programming solution that finds the best subsequence.

Now, you need to design a divide and conquer algorithm for the same problem that is also optimal (so it needs to find the maximum value, not something approximate).  It is acceptable for the time complexity of your algorithm to be larger than O(n).  If you can show an O(n²) algorithm, you get 5+ points.  If you show O(n log n) algorithm, you get 10 points.  [If your algorithm is w(n²), that is sadly not worth anything. L]

Answer 1

We use D&C

Divide the array into two halfs:

Left side recursive call: T(n/2) time to find MVCS in A[1..n/2]

Right side recursive call: T(n/2) time to find MVCS in A[n/2 + 1..n]

If we can solve the "left-right" case in O(n) time, we will have our T(n) = 2 T(n/2) + O(n) recurrence relation, which then leads to T(n) = O(n log n) analysis.

How to solve the boundary case in O(n) time

To solve boundary case, we realize, that it must include both A[n/2] and A[n/2 + 1].  We simply find the maximum in both directions and add those up.  For example:

rightMax = MINUS_INFINITY

rightSum = 0

for (j = n/2 + 1 to n) {

   rightSum += a[j]

   rightMax = max(rightMax, rightSum)

}

This finds the rightMax.  Similarly we find leftMax

middleMax is then simply leftMax + rightMax

Overall algorithm can be written as:

MVCS(A,1,n) {

  leftOnlyMax = MVCS(A,1,n/2)

  rightOnlyMax = MVCS(A,n/2+1,n)

  middleMax = as calculated in the merge routine above

  overallMax = max(leftOnlyMax, rightOnlyMax, middleMax);

  return overallMax

}