Programa C++ para líderes en una array

Escriba un programa para imprimir todos los LÍDERES en la array. Un elemento es líder si es mayor que todos los elementos a su lado derecho. Y el elemento más a la derecha es siempre un líder. Por ejemplo, en el arreglo {16, 17, 4, 3, 5, 2}, los líderes son 17, 5 y 2. 
Deje que el arreglo de entrada sea arr[] y el tamaño del arreglo sea size .
 

Método 1 (Simple) 
Use dos bucles. El ciclo externo va desde 0 hasta tamaño – 1 y uno por uno selecciona todos los elementos de izquierda a derecha. El bucle interno compara el elemento elegido con todos los elementos de su lado derecho. Si el elemento seleccionado es mayor que todos los elementos a su lado derecho, entonces el elemento seleccionado es el líder. 
 

#include<iostream>
using namespace std;
  
/*C++ Function to print leaders in an array */
void printLeaders(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        int j;
        for (j = i+1; j < size; j++)
        {
            if (arr[i] <=arr[j])
                break;
        }    
        if (j == size) // the loop didn't break
            cout << arr[i] << " ";
  }
}
  
/* Driver program to test above function */
int main()
{
    int arr[] = {16, 17, 4, 3, 5, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    printLeaders(arr, n);
    return 0;
}

Producción: 

17 5 2

Complejidad de tiempo: O(n*n)
Método 2 (Escanear desde la derecha) 
Escanee todos los elementos de derecha a izquierda en una array y realice un seguimiento del máximo hasta ahora. Cuando el máximo cambie su valor, imprímalo.
La imagen de abajo es una ejecución en seco del enfoque anterior:
 

A continuación se muestra la implementación del enfoque anterior:
 

#include <iostream>
using namespace std;
  
/* C++ Function to print leaders in an array */
void printLeaders(int arr[], int size)
{
    int max_from_right =  arr[size-1];
  
    /* Rightmost element is always leader */
    cout << max_from_right << " ";
      
    for (int i = size-2; i >= 0; i--)
    {
        if (max_from_right < arr[i]) 
        {           
            max_from_right = arr[i];
            cout << max_from_right << " ";
        }
    }    
}
  
/* Driver program to test above function*/
int main()
{
    int arr[] = {16, 17, 4, 3, 5, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    printLeaders(arr, n);
    return 0;
}    

Producción:

2 5 17

Complejidad de tiempo: O(n)
 

Consulte el artículo completo sobre Líderes en una array para obtener más detalles.