C++ 分治算法求数组的最大元素

Divide and conquer algorithms to find the maximum element of an array

提问by dato datuashvili

I am trying to understand how the following algorithms works.

我试图了解以下算法的工作原理。

#include <iostream>
using namespace std;
int maxsimum(int a[], int l, int r) {
    if (l == r)  
        return a[l];
    int m = (l+r)/2;
    int u = maxsimum(a,l,m);
    int v = maxsimum(a,m+1,r);
    return u>v?u:v;    
}

int main() {
    int a[] = {34,23,45,56,30,31,57,33,55,10};
    int n = sizeof(a)/sizeof(int);
    cout << maxsimum(a,0,n) << endl;         
    return 0;
}

First, what I am interested in is that in spite of algorithm's working correctly, it is mysterious for me how it finds the maximum element. I will show how I understood this algorithm:

首先，我感兴趣的是尽管算法工作正常，但它如何找到最大元素对我来说很神秘。我将展示我如何理解这个算法：

Step 1: we say that in case of an array, l=0and r=10, it checks if (l>r)which does not hold of course so it calculates m=(0+10)/2;. Then do again the procedure for new bounds. The first pair is (0,5), the second is (6,10) and after the final operation it compares two returned values and finally returns the maximum element between them.

第 1 步：我们说，在数组l=0和 的情况下r=10，它检查if (l>r)哪个当然不成立，因此它计算m=(0+10)/2;。然后再次执行新边界的过程。第一对是 (0,5)，第二对是 (6,10) 并且在最终操作之后它比较两个返回值并最终返回它们之间的最大元素。

Does this algorithm always work? In each iteration it does not do any comparison, only the final step. How can it determine the maximum element at each recursive iteration? It checks only what. For example: take pair(0,5), is (0 more than 5)? No, so repeat again and divide these bounds into two so get new average value m1=(0+5)/2 then again again and return some element but not the maximum. Also for second subarray we can say the same.

这个算法总是有效吗？在每次迭代中它不做任何比较，只做最后一步。它如何确定每次递归迭代的最大元素？它只检查什么。例如：取pair(0,5)，是(0大于5)吗？不，所以再次重复并将这些边界分成两部分，以便获得新的平均值 m1=(0+5)/2 然后再次返回一些元素但不是最大值。对于第二个子阵列，我们也可以这样说。

What is the main idea of this algorithm?

这个算法的主要思想是什么？

回答by Jeffrey Sax

Your confusion is understandable: the algorithm as written contains a couple of bugs. It accesses memory past the end of a, which is very, very bad. Also, the test whether a range contains only one element is incorrect. If not addressed, this leads to a stack overflow.

您的困惑是可以理解的：所编写的算法包含一些错误。它访问 a 末尾之后的内存，这是非常非常糟糕的。此外，测试一个范围是否只包含一个元素是不正确的。如果不解决，这会导致堆栈溢出。

The way the maxsimum function is called suggests that the lower bound is included in the range, but the upper bound is not. a[0]is valid, but a[n]accesses memory past the end of a. When splitting the range, we want the first part to run from l up to but not including m, and the second part to start at m and run up to but not include r. In other words: the "exclusive" upper limit of the first part is equal to the "inclusive" lower limit of the second part. The first internal call to maxsimum is correct. The second internal call should be:

调用 maxsimum 函数的方式表明范围内包含下限，但不包含上限。a[0]是有效的，但a[n]访问的内存超过 a 的结尾。分割范围时，我们希望第一部分从 l 开始运行，但不包括 m，第二部分从 m 开始运行，但不包括 r。换句话说：第一部分的“不包括”上限等于第二部分的“包括”下限。对 maxsimum 的第一个内部调用是正确的。第二个内部调用应该是：

int v=maxsimum(a,m,r); 

This leaves us with the problem of detecting a range of length 1. As it stands, the algorithm actually looks for an emptyrange. The proper test is to look at the difference between the upper and the lower bound:

这给我们留下了检测长度为 1 的范围的问题。就目前而言，该算法实际上寻找一个空范围。正确的测试是查看上限和下限之间的差异：

if (r-l == 1) return a[l];

The complete function is as follows:

完整的功能如下：

int maxsimum(int a[],int l,int r){
   if (r-l==1)  return a[l];
   int m=(l+r)/2;
   int u=maxsimum(a,l,m);
   int v=maxsimum(a,m,r);
   return u>v?u:v;    
}

Now that we have a correct program, the explanation of how this works is straightforward:

现在我们有了一个正确的程序，它是如何工作的解释很简单：

1. If the range contains only one element, then this element is the maximum.
2. If the range contains more than one element, we split it in two parts. We call the function recursively to compute the maximum of each part. The maximum of these two values is the maximum of the entire range.

1. 如果范围仅包含一个元素，则此元素为最大值。
2. 如果范围包含多个元素，我们将其分为两部分。我们递归调用该函数来计算每个部分的最大值。这两个值中的最大值是整个范围的最大值。

回答by Simone

The main idea is that if we divide the array in 2 subarrays, then the maximum must be in the left or in the right part of the array; there's no other possibility.

主要思想是，如果我们将数组划分为 2 个子数组，那么最大值必须在数组的左侧或右侧；没有其他可能。

So we find the maximum in the left part, we find the maximum in the right part and the global maximum will obviously be the maximum between the two maximum, that is what is returned by the last line of the maxsimum function.

所以我们在左边找到最大值，在右边找到最大值，全局最大值显然是两个最大值之间的最大值，这就是 maxsimum 函数的最后一行返回的值。

回答by Konrad Rudolph

Your error is here:

你的错误在这里：

In each iteration it does not do any comparison, only the final step.

在每次迭代中它不做任何比较，只做最后一步。

This is wrong. In fact, it does a comparison in everystep of the recursion (except in the base cases, i.e. where the array size is 1).

这是错误的。事实上，它在递归的每一步都进行比较（除了基本情况，即数组大小为 1 的情况）。

回答by daramarak

Let me comment the maximum part of the code for you, and try not to add confusion:

让我为您注释代码的最大部分，并尽量不要添加混淆：

if (l==r)  return a[l]; //trivial case, if there is only one value in the array return it
int m=(l+r)/2; //find value halfway into the array
int u=maxsimum(a,l,m); //find the maximum value for the lower part of the array
int v=maxsimum(a,m+1,r); //find the maximum value for the top part of the array
return u>v?u:v; //return the highest value of them.

So the array 0..10 is splitted into 0..5 and 6..10 and passed into the same function. Only when there is only one value the recursion ends and that single value is passed to their callees. Then in the second lowest cases, like value a[0] and a[1] it will do the first comparisons. The results of these will be passed up to the higher cases until it will exit the function for the final time returning with the largest value of all the cases.

因此数组 0..10 被拆分为 0..5 和 6..10 并传递给同一个函数。只有当只有一个值时，递归才会结束，并将该单个值传递给它们的被调用者。然后在次低的情况下，如值 a[0] 和 a[1]，它将进行第一次比较。这些结果将被传递给更高的案例，直到它以所有案例中的最大值返回最后一次退出函数。

I hope was able clarify a bit for you.

我希望能够为你澄清一点。

回答by alex

Error in main()function, test array has 10 elements, should be:

main()函数错误，测试数组有10个元素，应该是：

cout << maxsimum(a,0,n-1) << endl;

回答by Kishy Nivas

This answer might be so late, but it may be useful to someone to grasp the recursion calls, I modified the above code to trace out the function calls. After seeing the output it is easy to see how a recursive tree is made.

这个答案可能太晚了，但它可能对某人掌握递归调用有用，我修改了上面的代码以跟踪函数调用。看到输出后，很容易看到递归树是如何制作的。

#include <iostream>
using namespace std;
int maxsimum(int a[], int l, int r) {
if (l == r)  
    return a[l];
int m = (l+r)/2;

cout<<"values gonna get computed in 1st recursive call"<< l<<" "<< m<<"\n";
int u = maxsimum(a,l,m);

cout<<"value of u "<<u<<"\n";

cout<<"value gonna get computed in 2nd recursion  call "<<m+1 <<" "<<r<<"\n";
int v = maxsimum(a,m+1,r);

cout<<"value of v : "<<v<<"\n";
cout<<"current u value :"<<u <<"current v value "<<v <<"\n";

return u>v?u:v;    
}

int main() {
int a[] = {5,6,7,8,9};
int n = sizeof(a)/sizeof(int);
cout << maxsimum(a,0,n-1) << endl;         
return 0;
}

Here is the recursion tree for the above program, the tree first goes towards the left side i.e for the first recursive statement, then each call returns its base value, the return condition makes sure only the maximum element is selected in each calls.

这是上述程序的递归树，树首先向左移动，即第一个递归语句，然后每次调用返回其基值，返回条件确保在每次调用中只选择最大元素。

                 (9)  
                (0,4)
              /      \
           7 /        
        (0,2)          (3,4)
         /  \          /    \
       6/          8/      
       (0,1)  (2,2)  (3,3)     (4,4) 
        / \      
      5/   
     (0,0) (1,1)