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
– j_random_hacker, Commented Oct 11, 2016 at 12:13

Alexey Guseynov · Accepted Answer · 2016-10-10 20:51:35Z

1

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;
    }
}

answered Oct 10, 2016 at 20:51

Alexey Guseynov

5,3441 gold badge24 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Bibek Bhattarai Over a year ago

I know, I can do it with single pass of array. I just wanted to know how to do it using divide and conquer approach. Thanks for answer anyway :)

E B Over a year ago

@BibekBhattarai when you said fixed sized maximum sub-array you mean given a size l where l<n find the maximum sum of l consecutive elements correct?

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related