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.