Maximice el primer elemento de Array eliminando primero o agregando un elemento previamente eliminado

Dada una array arr[] de tamaño N y un número entero K , la tarea es maximizar el primer elemento de la array en K operaciones donde en cada operación:

• Si la array no está vacía, elimine el elemento superior de la array.
• Agregue cualquiera de los elementos eliminados anteriormente al comienzo de la array.

Ejemplos:

Entrada: arr[] = [5, 2, 2, 4, 0, 6], K = 4
Salida: 5
Explicación: Las 4 operaciones son como:

• Eliminar el elemento superior = 5. El arr se convierte en [2, 2, 4, 0, 6].
• Eliminar el elemento superior = 2. El arr se convierte en [2, 4, 0, 6].
• Eliminar el elemento superior = 2. El arr se convierte en [4, 0, 6].
• Agregue 5 de nuevo en el arr. El arr se convierte en [5, 4, 0, 6].

Aquí 5 es la mayor respuesta posible después de 4 movimientos.

Entrada: arr[] = [2], K = 1
Salida: -1
Explicación: Solo se puede aplicar un movimiento y en el primer movimiento. 
La única opción es eliminar el primer elemento de arr[]. 
Si se hace eso, la array se vuelve vacía. Entonces la respuesta es -1

Enfoque: Este problema se puede resolver con la ayuda del enfoque Greedy basado en la siguiente idea:

En primeras operaciones K- 1 , se puede quitar el valor K-1 del arranque . Así que actualmente en el Node Kth. Ahora en la última operación hay dos opciones posibles:

• Quite el Node de inicio actual (óptimo si el valor del (K+1)ésimo Node es mayor que el más grande entre los primeros elementos K-1 ya eliminados)
• Agregue el más grande de los elementos K-1 ya eliminados (óptimo cuando el (K + 1) Node tiene menos valor que este más grande)

Siga la ilustración que se muestra a continuación para una mejor comprensión.

Ilustración:

Por ejemplo arr[] = {5, 2, 2, 4, 0, 6}, K = 4

1ra Operación:
        => Quitar 5. arr[] = {2, 2, 4, 0, 6}
        => máximo = 5 , K = 4 – 1 = 3

2.ª operación:
        => Quitar 2. arr[] = {2, 4, 0, 6}
        => máximo = máx (5, 2) = 5 , K = 3 – 1 = 2

3ra Operación:
        => Quitar 2. arr[] = {4, 0, 6}
        => máximo = max (5, 2) = 5 , K = 2 – 1 = 1

Cuarta operación:
        => Aquí el segundo elemento actual, es decir, 0 es menor que 5.
        => Así que agregue 5 nuevamente en la array. arr[] = {5, 4, 0, 6}
        => máximo = max (5, 0) = 5 , K = 1 – 1 = 0

Por lo tanto, el primer elemento máximo posible es 5 .

Siga los pasos para resolver el problema:

• Si K = 0 , devuelva el valor del primer Node.
• Si K = 1 , devuelva el valor del segundo Node (si lo hay), de lo contrario, devuelva -1 (porque después de K operaciones, la lista no existe).
• Si el tamaño de la lista enlazada es uno, entonces en cada operación impar (es decir, 1, 3, 5, . . . ), devuelve -1, de lo contrario, devuelve el valor del primer Node (porque si se realiza una operación impar, la array quedará vacía).
• Si K > 2 , entonces:
  • Atraviese los primeros Nodes K-1 y descubra el valor máximo.
  • Compare ese valor máximo con el valor del Node (K+1) .
  • Si el valor (K+1)th es mayor que el valor máximo anterior, actualícelo con el valor del Node (K+1)th . De lo contrario, no actualice el valor máximo.
• Devuelve el valor máximo.

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

// C++ code to implement the approach
#include <iostream>
using namespace std;
 
int maximumTopMost(int arr[], int k,int N){
 
   // Checking if k is odd and
    // length of array is 1
    if (N == 1 and k % 2 != 0)
        return -1;
 
    // Initializing ans with -1
    int ans = -1;
 
    // If k is greater or equal to the
    // length of array
    for(int i  = 0; i <  min(N, k - 1); i++)
        ans = max(ans, arr[i]);
 
    // If k is less than length of array
    if (k < N)
        ans = max(ans, arr[k]);
 
    // Returning ans
    return ans;
}
 
// Driver code
int main() {
 
      int arr[] = {5, 2, 2, 4, 0, 6};
      int N = 6;
      int K = 4;
      cout <<(maximumTopMost(arr, K, N));
      return 0;
}
 
// This code is contributed by hrithikgarg03188.

// Java code to implement the approach
class GFG {
 
  static int maximumTopMost(int[] arr, int k, int N)
  {
 
    // Checking if k is odd and
    // length of array is 1
    if (N == 1 && k % 2 != 0)
      return -1;
 
    // Initializing ans with -1
    int ans = -1;
 
    // If k is greater or equal to the
    // length of array
    for (int i = 0; i < Math.min(N, k - 1); i++)
      ans = Math.max(ans, arr[i]);
 
    // If k is less than length of array
    if (k < N)
      ans = Math.max(ans, arr[k]);
 
    // Returning ans
    return ans;
  }
  public static void main(String[] args)
  {
 
    int[] arr = { 5, 2, 2, 4, 0, 6 };
    int N = 6;
    int K = 4;
    System.out.println(maximumTopMost(arr, K, N));
  }
}
 
// This code is contributed by phasing17.

# Python code to implement the approach
 
def maximumTopMost(arr, k):
 
    # Checking if k is odd and
    # length of array is 1
    if len(arr) == 1 and k % 2 != 0:
        return -1
 
    # Initializing ans with -1
    ans = -1
 
    # If k is greater or equal to the
    # length of array
    for i in range(min(len(arr), k - 1)):
        ans = max(ans, arr[i])
 
    # If k is less than length of array
    if k < len(arr):
        ans = max(ans, arr[k])
 
    # Returning ans
    return ans
 
 
# Driver code
if __name__ == "__main__":
    arr = [5, 2, 2, 4, 0, 6]
    K = 4
    print(maximumTopMost(arr, K))

// C# code to implement the approach
using System;
class GFG {
 
  static int maximumTopMost(int[] arr, int k, int N)
  {
 
    // Checking if k is odd and
    // length of array is 1
    if (N == 1 && k % 2 != 0)
      return -1;
 
    // Initializing ans with -1
    int ans = -1;
 
    // If k is greater or equal to the
    // length of array
    for (int i = 0; i < Math.Min(N, k - 1); i++)
      ans = Math.Max(ans, arr[i]);
 
    // If k is less than length of array
    if (k < N)
      ans = Math.Max(ans, arr[k]);
 
    // Returning ans
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
 
    int[] arr = { 5, 2, 2, 4, 0, 6 };
    int N = 6;
    int K = 4;
    Console.Write(maximumTopMost(arr, K, N));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript code to implement the approach
 
    const maximumTopMost = (arr, k) => {
        // Checking if k is odd and
        // length of array is 1
        if (arr.length == 1 && k % 2 != 0)
            return -1;
 
        // Initializing ans with -1
        let ans = -1;
 
        // If k is greater or equal to the
        // length of array
        for (let i = 0; i < Math.min(arr.length, k - 1); ++i)
            ans = Math.max(ans, arr[i]);
 
        // If k is less than length of array
        if (k < arr.length)
            ans = Math.max(ans, arr[k]);
 
        // Returning ans
        return ans;
    }
 
 
    // Driver code
    let arr = [5, 2, 2, 4, 0, 6];
    let K = 4;
    document.write(maximumTopMost(arr, K));
 
// This code is contributed by rakeshsahni
 
</script>

5

Complejidad temporal: O(N)
Espacio auxiliar: O(1)