Алгоритм «разделяй и властвуй», чтобы найти положение максимального элемента

Question

Я пытаюсь найти индекс элемента max в массиве, используя алгоритм «разделяй и властвуй». В настоящее время выходные данные правильно выводят максимальное значение моего массива, но я не могу понять, как передать позицию этого максимального элемента.

#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, который содержит оба значения массива & position .

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