Encuentre el elemento máximo en la array que no sea Ai

Dada una array arr[] de tamaño N . La tarea es encontrar el elemento máximo entre N – 1 elementos que no sean arr [i] para cada i de 1 a N.
Ejemplos: 
 

Entrada: arr[] = {2, 5, 6, 1, 3} 
Salida: 6 6 5 6 6 
Entrada: arr[] = {1, 2, 3} 
Salida: 3 3 2 
 

Enfoque: un enfoque eficiente es hacer una array de prefijos y sufijos de elementos máximos y encontrar el elemento máximo entre N – 1 elementos que no sean arr[i] .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum element
// among (N - 1) elements other than
// a[i] for each i from 1 to N
int max_element(int a[], int n)
{
    // To store prefix max element
    int pre[n];
 
    pre[0] = a[0];
    for (int i = 1; i < n; i++)
        pre[i] = max(pre[i - 1], a[i]);
 
    // To store suffix max element
    int suf[n];
 
    suf[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--)
        suf[i] = max(suf[i + 1], a[i]);
 
    // Find the maximum element
    // in the array other than a[i]
    for (int i = 0; i < n; i++) {
        if (i == 0)
            cout << suf[i + 1] << " ";
 
        else if (i == n - 1)
            cout << pre[i - 1] << " ";
 
        else
            cout << max(pre[i - 1], suf[i + 1]) << " ";
    }
}
 
// Driver code
int main()
{
    int a[] = { 2, 5, 6, 1, 3 };
    int n = sizeof(a) / sizeof(a[0]);
 
    max_element(a, n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// Function to find maximum element
// among (N - 1) elements other than
// a[i] for each i from 1 to N
static void max_element(int a[], int n)
{
    // To store prefix max element
    int []pre = new int[n];
 
    pre[0] = a[0];
    for (int i = 1; i < n; i++)
        pre[i] = Math.max(pre[i - 1], a[i]);
 
    // To store suffix max element
    int []suf = new int[n];
 
    suf[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--)
        suf[i] = Math.max(suf[i + 1], a[i]);
 
    // Find the maximum element
    // in the array other than a[i]
    for (int i = 0; i < n; i++)
    {
        if (i == 0)
            System.out.print(suf[i + 1] + " ");
 
        else if (i == n - 1)
            System.out.print(pre[i - 1] + " ");
 
        else
            System.out.print(Math.max(pre[i - 1],
                              suf[i + 1]) + " ");
    }
}
 
// Driver code
public static void main(String []args)
{
    int a[] = { 2, 5, 6, 1, 3 };
    int n = a.length;
 
    max_element(a, n);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 implementation of the approach
 
# Function to find maximum element
# among (N - 1) elements other than
# a[i] for each i from 1 to N
def max_element(a, n) :
 
    # To store prefix max element
    pre = [0] * n;
 
    pre[0] = a[0];
    for i in range(1, n) :
        pre[i] = max(pre[i - 1], a[i]);
 
    # To store suffix max element
    suf = [0] * n;
 
    suf[n - 1] = a[n - 1];
    for i in range(n - 2, -1, -1) :
        suf[i] = max(suf[i + 1], a[i]);
 
    # Find the maximum element
    # in the array other than a[i]
    for i in range(n) :
        if (i == 0) :
            print(suf[i + 1], end = " ");
 
        elif (i == n - 1) :
            print(pre[i - 1], end = " ");
 
        else :
            print(max(pre[i - 1],
                      suf[i + 1]), end = " ");
 
# Driver code
if __name__ == "__main__" :
 
    a = [ 2, 5, 6, 1, 3 ];
    n = len(a);
 
    max_element(a, n);
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to find maximum element
// among (N - 1) elements other than
// a[i] for each i from 1 to N
static void max_element(int []a, int n)
{
    // To store prefix max element
    int []pre = new int[n];
 
    pre[0] = a[0];
    for (int i = 1; i < n; i++)
        pre[i] = Math.Max(pre[i - 1], a[i]);
 
    // To store suffix max element
    int []suf = new int[n];
 
    suf[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--)
        suf[i] = Math.Max(suf[i + 1], a[i]);
 
    // Find the maximum element
    // in the array other than a[i]
    for (int i = 0; i < n; i++)
    {
        if (i == 0)
            Console.Write(suf[i + 1] + " ");
 
        else if (i == n - 1)
            Console.Write(pre[i - 1] + " ");
 
        else
            Console.Write(Math.Max(pre[i - 1],
                           suf[i + 1]) + " ");
    }
}
 
// Driver code
public static void Main(String []args)
{
    int []a = { 2, 5, 6, 1, 3 };
    int n = a.Length;
 
    max_element(a, n);
}
}
 
// This code is contributed by PrinciRaj1992

<script>
// Javascript implementation of the approach
 
// Function to find maximum element
// among (N - 1) elements other than
// a[i] for each i from 1 to N
function max_element(a, n)
{
 
    // To store prefix max element
    let pre = new Array(n);
 
    pre[0] = a[0];
    for (let i = 1; i < n; i++)
        pre[i] = Math.max(pre[i - 1], a[i]);
 
    // To store suffix max element
    let suf = new Array(n);
 
    suf[n - 1] = a[n - 1];
    for (let i = n - 2; i >= 0; i--)
        suf[i] = Math.max(suf[i + 1], a[i]);
 
    // Find the maximum element
    // in the array other than a[i]
    for (let i = 0; i < n; i++) {
        if (i == 0)
            document.write(suf[i + 1] + " ");
 
        else if (i == n - 1)
            document.write(pre[i - 1] + " ");
 
        else
            document.write(Math.max(pre[i - 1], suf[i + 1]) + " ");
    }
}
 
// Driver code
let a = [2, 5, 6, 1, 3];
let n = a.length;
max_element(a, n);
 
// This code is contributed by _saurabh_jaiswal
</script>

6 6 5 6 6

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(n)