Maximice el recuento de subarreglos que contienen el elemento Array máximo y mínimo después de eliminar como máximo un elemento

Posted on by Rudeus Greyrat

Dada una array arr[] de tamaño N . La tarea es maximizar el recuento de subarreglos que contienen los elementos mínimo y máximo del arreglo eliminando como máximo un elemento del arreglo.

Ejemplos: 
 

Entrada: arr[] = {7, 2, 5, 4, 3, 1} 
Salida: 4 
Explicación: 
elimine 1 de la array, la array resultante será {7, 2, 5, 4, 3}. Entonces, el número de subarreglos que contienen el elemento máximo 7 y el elemento mínimo 2 será 4 {[7, 2], [7, 2, 5], [7, 2, 5, 4], [7, 2, 5, 4 , 3]} 
 

Entrada: arr[] = {9, 9, 8, 9, 8, 9, 9, 8, 9, 8} 
Salida: 43

Enfoque ingenuo: el enfoque más simple es eliminar todos los elementos y luego contar el número de subarreglos que tienen el elemento mínimo y máximo del arreglo resultante.

Complejidad de Tiempo: O(N 3 ) 
Espacio Auxiliar: O(1)
 

Enfoque eficiente: este enfoque se basa en la observación de que la eliminación de elementos que no sean el elemento máximo o mínimo nunca maximiza el resultado general. A continuación se muestran los pasos: 
 

  1. Inicialice el resultado general con INT_MIN.
  2. Cree una función, digamos proc , que devuelva la cantidad de subarreglos que contienen el elemento más pequeño y el más grande de la array.
  3. Para calcular el número de subarreglos, encuentre el índice inicial y final del subarreglo utilizando el enfoque de dos punteros :
    • Inicialice el elemento más pequeño y el más grande, digamos bajo y alto con el último elemento de la array.
    • Inicialice dos punteros p1 y p2 con el último índice de la array que almacena la ubicación de low y high .
    • Ahora, itere sobre la array y verifique si el elemento actual es menor que bajo , luego actualice p1 .
    • Si el elemento actual es más que alto , actualice p2 .
    • En cada paso, actualice el número máximo de subarreglos.
  4. Ahora, calcule el número de subarreglos en los siguientes tres casos: 
    • Sin quitar ningún elemento 
       
    • Después de eliminar el elemento más grande
    • Después de quitar el elemento más pequeño.
  5. Tome el máximo de los tres casos.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Returns the count of subarrays
// which contains both the maximum and
// minimum elements in the given vector
long long proc(vector<int> &v)
    {
   
        long long int n = v.size();
   
        // Initialize the low and
        // high of array
        int low = v[n - 1], high = v[n - 1];
        long long int p1 = n, p2 = n;
        long long ans = 0;
   
        for (int i = n - 1; i >= 0; i--) {
            int x = v[i];
   
            // If current element is
            // less than least element
            if (x < low) {
                low = x;
                ans = 0;
            }
   
            // If current element is
            // more than highest element
            else if (x > high) {
                high = x;
                ans = 0;
            }
   
            // If current element is
            // equal to low or high
            // then update the pointers
            if (x == low)
                p1 = i;
            if (x == high)
                p2 = i;
   
            // Update number of subarrays
            ans += n - max(p1, p2);
        }
   
        // Return the result
        return ans;
    }
  
// Function to find the maximum
    // count of subarrays
long long subarray(vector<int>& v)
{
    long long int n=v.size();
    if(n<=1)
    return n;
    long long ans=proc(v);
    int low=v[0],pos_low=0,high=v[0],pos_high=0;
    // Iterate the array to find
    // the maximum and minimum element
    for (int i = 1; i < n; i++) {
            int x = v[i];
            if (x < low) {
                low = x;
                pos_low = i;
            }
            else if (x > high) {
                high = x;
                pos_high = i;
            }
        }
        // Vector after removing the
        // minimum element
        vector<int>u;
         // Using assignment operator to copy one
         //  vector to other
         u=v;
         u.erase(u.begin()+pos_low);
         ans=max(ans,proc(u));
         // Vector after removing the
        // maximum element
        vector<int>w;
        w=v;
        w.erase(w.begin()+pos_high);
        return max(ans,proc(w));
     
}
 
// Driver Code
int main()
{
   
    // Given array
    vector<int>v;
    v.push_back(7);
    v.push_back(2);
    v.push_back(5);
    v.push_back(4);
    v.push_back(3);
    v.push_back(1);
   
  // Function Call
  cout<<subarray(v)<<endl;
  
    return 0;
}
// This code is contributed by dwivediyash

Java

// Java implementation of the above approach
import java.util.*;
import java.lang.*;
 
class GFG {
 
    // Function to find the maximum
    // count of subarrays
    static long subarray(List<Integer> v)
    {
        int n = v.size();
        if (n <= 1)
            return n;
 
        long ans = proc(v);
        int low = v.get(0), pos_low = 0;
        int high = v.get(0), pos_high = 0;
 
        // Iterate the array to find
        // the maximum and minimum element
        for (int i = 1; i < n; i++) {
            int x = v.get(i);
            if (x < low) {
                low = x;
                pos_low = i;
            }
            else if (x > high) {
                high = x;
                pos_high = i;
            }
        }
 
        // List after removing the
        // minimum element
        List<Integer> u
            = new ArrayList<>(
                Collections.nCopies(n, 0));
        Collections.copy(u, v);
        u.remove(pos_low);
        ans = Math.max(ans, proc(u));
 
        // List after removing the
        // maximum element
        List<Integer> w
            = new ArrayList<>(
                Collections.nCopies(n, 0));
        Collections.copy(w, v);
        w.remove(pos_high);
 
        return Math.max(ans, proc(w));
    }
 
    // Returns the count of subarrays
    // which contains both the maximum and
    // minimum elements in the given list
    static long proc(List<Integer> v)
    {
 
        int n = v.size();
 
        // Initialize the low and
        // high of array
        int low = v.get(n - 1), high = v.get(n - 1);
        int p1 = n, p2 = n;
        long ans = 0;
 
        for (int i = n - 1; i >= 0; i--) {
            int x = v.get(i);
 
            // If current element is
            // less than least element
            if (x < low) {
                low = x;
                ans = 0;
            }
 
            // If current element is
            // more than highest element
            else if (x > high) {
                high = x;
                ans = 0;
            }
 
            // If current element is
            // equal to low or high
            // then update the pointers
            if (x == low)
                p1 = i;
            if (x == high)
                p2 = i;
 
            // Update number of subarrays
            ans += n - Math.max(p1, p2);
        }
 
        // Return the result
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given array
        List<Integer> arr = Arrays.asList(7, 2, 5, 4, 3, 1);
 
        // Function Call
        System.out.println(subarray(arr));
    }
}

Python3

# Python program for the above approach
 
# Returns the count of subarrays
# which contains both the maximum and
# minimum elements in the given vector
def proc(v):
  n = len(v);
 
  # Initialize the low and
  # high of array
  low = v[n - 1]
  high = v[n - 1]
  p1 = n
  p2 = n;
  ans = 0;
 
  for i in range(n - 1, -1, -1):
    x = v[i];
 
    # If current element is
    # less than least element
    if (x < low):
      low = x;
      ans = 0;
     
    # If current element is
    # more than highest element
    elif (x > high):
      high = x;
      ans = 0;
     
    # If current element is
    # equal to low or high
    # then update the pointers
    if (x == low): p1 = i;
    if (x == high): p2 = i;
 
    # Update number of subarrays
    ans += n - max(p1, p2);
   
  # Return the result
  return ans;
 
# Function to find the maximum
# count of subarrays
def subarray(v):
  n = len(v);
 
  if (n <= 1):
    return n;
   
  ans = proc(v);
  low = v[0]
  pos_low = 0
  high = v[0]
  pos_high = 0
     
  # Iterate the array to find
  # the maximum and minimum element
  for i in range(1, n):
    x = v[i];
    if (x < low):
      low = x;
      pos_low = i;
    elif (x > high):
      high = x;
      pos_high = i;
     
  # Vector after removing the
  # minimum element
  u = v[:];
   
  # Using assignment operator to copy one
  #  vector to other
  del u[pos_low];
 
  ans = max(ans, proc(u));
 
  # Vector after removing the
  # maximum element
  w = v[:];
 
  del w[pos_high];
  return max(ans, proc(w));
 
# Driver Code
 
# Given array
v = [];
v.append(7);
v.append(2);
v.append(5);
v.append(4);
v.append(3);
v.append(1);
 
# Function Call
print(subarray(v));
 
# This code is contributed by gfgking

C#

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
    // Function to find the maximum
    // count of subarrays
    static long subarray(List<int> v)
    {
        int n = v.Count;
        if (n <= 1){
            return n;
        }
 
        long ans = proc(v);
        int low = v[0], pos_low = 0;
        int high = v[0], pos_high = 0;
 
        // Iterate the array to find
        // the maximum and minimum element
        for (int i = 1 ; i < n ; i++) {
            int x = v[i];
            if (x < low) {
                low = x;
                pos_low = i;
            }
            else if (x > high) {
                high = x;
                pos_high = i;
            }
        }
 
        // List after removing the
        // minimum element
        List<int> u = new List<int>();
        for(int i = 0 ; i < n ; i++){
            u.Add(0);
        }
 
        u = new List<int>(v);
        u.Remove(v[pos_low]);
        ans = Math.Max(ans, proc(u));
 
        // List after removing the
        // maximum element
        List<int> w = new List<int>();
        for(int i = 0 ; i < n ; i++){
            w.Add(0);
        }
 
        w = new List<int>(v);
        w.Remove(v[pos_high]);
 
        return Math.Max(ans, proc(w));
    }
 
    // Returns the count of subarrays
    // which contains both the maximum and
    // minimum elements in the given list
    static long proc(List<int> v)
    {
 
        int n = v.Count;
 
        // Initialize the low and
        // high of array
        int low = v[n-1], high = v[n-1];
        int p1 = n, p2 = n;
        long ans = 0;
 
        for (int i = n - 1; i >= 0; i--) {
            int x = v[i];
            // If current element is
            // less than least element
            if (x < low) {
                low = x;
                ans = 0;
            }
 
            // If current element is
            // more than highest element
            else if (x > high) {
                high = x;
                ans = 0;
            }
 
            // If current element is
            // equal to low or high
            // then update the pointers
            if (x == low)
                p1 = i;
            if (x == high)
                p2 = i;
 
            // Update number of subarrays
            ans += n - Math.Max(p1, p2);
        }
 
        // Return the result
        return ans;
    }
 
    public static void Main(string[] args){
         
        // Given array
        List<int> arr = new List<int>{
            7, 2, 5, 4, 3, 1
        };
 
        // Function Call
        Console.WriteLine(subarray(arr));
 
    }
}
 
// This code is contributed by subhamgoyal2014.

Javascript

<script>
// Javascript program for the above approach
 
// Returns the count of subarrays
// which contains both the maximum and
// minimum elements in the given vector
function proc(v)
{
  let n = v.length;
 
  // Initialize the low and
  // high of array
  let low = v[n - 1],
    high = v[n - 1];
  let p1 = n,
    p2 = n;
  let ans = 0;
 
  for (let i = n - 1; i >= 0; i--) {
    let x = v[i];
 
    // If current element is
    // less than least element
    if (x < low) {
      low = x;
      ans = 0;
    }
 
    // If current element is
    // more than highest element
    else if (x > high) {
      high = x;
      ans = 0;
    }
 
    // If current element is
    // equal to low or high
    // then update the pointers
    if (x == low) p1 = i;
    if (x == high) p2 = i;
 
    // Update number of subarrays
    ans += n - Math.max(p1, p2);
  }
 
  // Return the result
  return ans;
}
 
// Function to find the maximum
// count of subarrays
function subarray(v) {
  let n = v.length;
 
  if (n <= 1) {
    return n;
  }
 
  let ans = proc(v);
  let low = v[0],
    pos_low = 0,
    high = v[0],
    pos_high = 0;
     
  // Iterate the array to find
  // the maximum and minimum element
  for (let i = 1; i < n; i++) {
    let x = v[i];
    if (x < low) {
      low = x;
      pos_low = i;
    } else if (x > high) {
      high = x;
      pos_high = i;
    }
  }
   
  // Vector after removing the
  // minimum element
  let u = [...v];
   
  // Using assignment operator to copy one
  //  vector to other
  u.splice(pos_low, 1);
 
  ans = Math.max(ans, proc(u));
 
  // Vector after removing the
  // maximum element
  let w = [...v];
 
  w.splice(pos_high, 1);
 
  return Math.max(ans, proc(w));
}
 
// Driver Code
 
// Given array
let v = [];
v.push(7);
v.push(2);
v.push(5);
v.push(4);
v.push(3);
v.push(1);
 
// Function Call
document.write(subarray(v));
 
// This code is contributed by gfgking
 
</script>
Producción 

4

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

Publicación traducida automáticamente

Artículo escrito por offbeat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *