分治算法寻找最大元素位置

Question

我正在尝试使用分治算法查找数组中最大元素的索引。目前，输出正确地输出了我的数组的最大值，但我无法弄清楚如何传递该最大元素的位置。

#include <iostream>

using namespace std;  


int maxElement(int a[], int l, int r) {
   if(r - l == 1) {
        cout << "R - L == 1 " <<  "Array value: " << a[l] << " Pos: " << l << endl;
        return a[l];
   }
   int m = (l + r) / 2;
   int u = maxElement(a, l, m);
   int v = maxElement(a, m, r);
   return u > v ? u : v;    
}

/* Driver program to test above functions */
int main() { 
    int Arr[] = {1, 4, 9, 3, 4, 9, 5, 6, 9, 3, 7};
    int arrSize = sizeof(Arr)/sizeof(Arr[0]); 

    cout << maxElement(Arr, 0, arrSize) << endl;
    return 0; 
} 

- DreadedSlug

---

如果您知道一个索引，您可以在O(1)时间内获取该值，但是如果您只知道值，则需要O(n)（最大）遍历整个数组并找到索引。要求“maxElement”返回索引而不是值。 - JohnFilleau

不要返回a[l]，而是返回l。然后，u和v变成了最大元素的索引。可以进行比较并返回a[u]>a[v]?u:v。 - TruthSeeker

这确实是一个不错的学术练习。但遗憾的是，它并没有真正做任何有用或非凡的事情。你无法摆脱比较数组中每个元素的基本要求。在这种情况下，这是由我们共同宇宙的一些基本物理定律所强制的要求，而所示的代码完成了这项任务。但是相同的任务也可以通过简单的“for”循环来完成。不需要递归。 - Sam Varshavchik

Answer 1

您可以返回一个包含数组值和位置的std::pair。

#include <iostream>
#include <utility>
using namespace std;  


std::pair<int, int> maxElement(int a[], int l, int r) {
   if(r - l == 1) {
        cout << "R - L == 1 " <<  "Array value: " << a[l] << " Pos: " << l << endl;
        return {a[l], l};
   }
   int m = (l + r) / 2;
   auto up = maxElement(a, l, m);
   auto vp = maxElement(a, m, r);
   return up.first > vp.first ? up : vp;    
}

/* Driver program to test above functions */
int main() { 
    int Arr[] = {1, 4, 9, 3, 4, 9, 5, 6, 9, 3, 7};
    int arrSize = sizeof(Arr)/sizeof(Arr[0]); 
    auto result = maxElement(Arr, 0, arrSize);
    cout << result.first << ", l = " << result.second << endl;
    return 0; 
} 

- aep

---

问题是如果最大值有重复怎么办？如果应该返回第一个最大值，那么你的修复方法就会失败（修复方法很简单）：https://godbolt.org/z/MbY9EM9M4 - Marek R

Answer 2

你可以使用这个方法来获取最大元素的索引，而不需要使用Pair。
希望这能对你有所帮助。

int DAC_Max_Postion(int arr[], int index, int l)
{
    int max;
    if(index >= l - 2)
    {
        if(arr[index] > arr[index + 1])
            return index;
        else
            return index + 1;
    }
    max = DAC_Max(arr, index + 1, l);
    if(arr[index] > arr[max])
        return index;
    else
        return max;
}

- Ahmed Fathy