分而治之算法找到最大元素的位置

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

Answer 1

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

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