如何解决“固定大小最大子阵列”问题？使用分而治之的方法？

问题描述

免责声明：我知道可以通过单次通过数组非常有效地解决此问题，但是我对使用分而治之的方法很感兴趣，因为它与我们通过分治解决的典型问题有些不同

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.

假设给定一个大小为n且间隔长度为l的浮点数组X [1：n]。问题是设计一种分而治之的算法，以从具有最大和的数组中找到长度为l的子数组。

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.

这是我想出的对于长度为n的数组，有l个连续元素的n-l + 1个子数组。例如，对于长度为n = 10且l = 3的数组，将有8个长度为3的子数组。

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.

现在，将问题分为两半，我决定在n-l + 1/2处中断数组，以便将相等数量的子数组分配给我的部门的两半，如下面的算法所示。同样，对于n = 10，l = 3，n-l + 1 = 8，所以我将问题划分为（n-l + 1）/ 2 =4。但是对于第4个子数组，我需要数组元素6即（n + l-1）/ 2。

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

注意：清除数组索引
对于从（n-l + 1）/ 2开始的子数组，我们需要直到（n-l + 1）/ 2 + l-1 =（n + l-1）/ 2

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

我的关注点：$ b​​ $ b为了应用分治法，我在两个数组中都使用了一些数据元素，因此我正在寻找另一种避免额外存储的方法。

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.

请忽略代码部分的语法，我只是在尝试介绍算法。 / p>

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

推荐答案

您不需要分而治之。一个简单的一遍算法可以用于该任务。假设这个数组足够大。然后：

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

这篇关于如何解决“固定大小最大子阵列”问题？使用分而治之的方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！