How to solve "fixed size maximum subarray" using divide and conquer approach?

Question

Disclaimer: I know this problem can be solved with single pass of array very efficiently, but I am interested in doing this with divide and conquer because it is bit different than typical problems we tackle with divide and conquer.

Suppose you are given a floating point array X[1:n] of size n and interval length l. The problem is to design a divide and conquer algorithm to find the sub-array of length l from the array that has the maximum sum.

Here is what I came up with.For array of length n there are n-l+1 sub-arrays of l consecutive elements. For example for array of length n = 10 and l = 3, there will be 8 sub-arrays of length 3.

Now, to divide the problem into two half, I decided to break array at n-l+1/2 so that equal number of sub-arrays will be distributed to both halves of my division as depicted in algorithm below. Again, for n = 10, l = 3, n-l+1 = 8, so I divided the problem at (n-l+1)/2 = 4. But for 4th sub-array I need array elements up-to 6 i.e. (n+l-1)/2.

void FixedLengthMS(input: X[1:n], l, output: k, max_sum)
{
   if(l==n){//only one sub-array
      sum = Sumof(X[1:n]);
      k=1;
   }
   int kl, kr;
   float sum_l, sum_r;
   FixedLengthMS(X[1:(n+l-1)/2], l, kl, sum_l);
   FixedLengthMS(X[(n-l+3)/2:n], l, kr, sum_r);

   if(sum_l >= sum_r){
      sum = sum_l;
      k = kl;
   }
   else{
      sum = sum_r;
      k = n-l+1/2 + kr;
   }
}

Note: to clear out array indexing for sub-array starting at (n-l+1)/2 we need array elements up-to (n-l+1)/2 + l-1 = (n+l-1)/2

My concern: To apply divide and conquer I have used some data elements in both array, so I am looking for another method that avoids the extra storage.

Faster method will be appreciated.

Please ignore the syntax of code section, I am just trying to give overview of algorithm.

Although the original maximum subarray problem can actually be solved nicely by D&C (doing this involves calculating, for any given interval, not just the max subarray in that interval but also the max subarray beginning at the left edge of the interval and the max subarray ending at the right edge; then a parent problem can compute its answers to these 3 questions using the 3+3=6 answers from its 2 subproblems), this variant (i.e., where the length l is fixed) problem is badly suited to D&C. I don't see how an O(n)-time D&C algorithm is possible, unless you restrict l to be o(n). — j_random_hacker

Alexey Guseynov Alexey Guseynov · Accepted Answer · 2016-10-10T20:51:35

You don't need divide and conquer. A simple one pass algorithm can be used for the task. Let's suppose, that array is big enough. Then:

double sum = 0;
for (size_t i = 0; i < l; ++i)
    sum += X[i];

size_t max_index = 0;
double max_sum = sum;

for (int i = 0; i < n - l; ++i) {
    sum += X[i + l] - X[i];
    if (sum > max_sum) {
        max_sum = sum;
        max_index = i;
    }
}

How to solve "fixed size maximum subarray" using divide and conquer approach?

1 Answers