Cuente los subarreglos que contienen el elemento de array máximo y mínimo

Dada una array arr[] que consta de N enteros distintos, la tarea es encontrar el número de subarreglos que contienen tanto el elemento máximo como el mínimo de la array dada.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4}
Salida: 1 
Explicación:  
Solo un único subarreglo {1, 2, 3, 4} consta del arreglo máximo (= 4) y mínimo (= 1) elementos.

Entrada: arr[] = {4, 1, 2, 3}
Salida: 3
Explicación:  
Los subarreglos {4, 1} , {4, 1, 2}, {4, 1, 2, 3} consisten en el máximo ( = 4) y los elementos de array mínimos (= 1).

Enfoque ingenuo: el enfoque más simple es primero, recorrer la array y encontrar el máximo y el mínimo de la array y luego generar todos los subarreglos posibles de la array dada . Para cada subarreglo, compruebe si contiene tanto el elemento de array máximo como el mínimo . Para todos esos subarreglos, aumente el conteo en 1. Finalmente, imprima el conteo de tales subarreglos.
Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente:  siga los pasos a continuación para optimizar el enfoque anterior:

• Encuentre el índice de los elementos máximo y mínimo . Sean i y j los respectivos índices tales que i < j .
• Todo el subarreglo que comienza desde los índices hasta i y termina en los índices después de j contendrá tanto el elemento de array máximo como el mínimo.
• Por lo tanto, los índices posibles para el índice inicial del subarreglo son [0, i] (total = i + 1 ).
• Por lo tanto, los posibles índices para el índice final del subarreglo son [j, N – 1]  (total = N – j ).
• Por lo tanto, el recuento de subarreglos viene dado por (i + 1) * (N – j) .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count subarray
// containing  both maximum and
// minimum array elements
int countSubArray(int arr[], int n)
{
    // If the length of the
    // array is less than 2
    if (n < 2)
        return n;
 
    // Find the index of maximum element
    int i
        = max_element(arr, arr + n) - arr;
 
    // Find the index of minimum element
    int j
        = min_element(arr, arr + n) - arr;
 
    // If i > j, then swap
    // the value of i and j
    if (i > j)
        swap(i, j);
 
    // Return the answer
    return (i + 1) * (n - j);
}
 
// Driver Code
int main()
{
    int arr[] = { 4, 1, 2, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    // Function call
    cout << countSubArray(arr, n);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
import java.lang.*;
 
class GFG{
     
// Function to count subarray
// containing both maximum and
// minimum array elements
static int countSubArray(int arr[], int n)
{
     
    // If the length of the
    // array is less than 2
    if (n < 2)
        return n;
 
    // Find the index of maximum element
    int i = max_element(arr);
 
    // Find the index of minimum element
    int j = min_element(arr);
 
    // If i > j, then swap
    // the value of i and j
    if (i > j)
    {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
         
    // Return the answer
    return (i + 1) * (n - j);
}
 
// Function to return max_element index
static int max_element(int[] arr)
{
    int idx = 0;
    int max = arr[0];
    for(int i = 1; i < arr.length; i++)
    {
        if(max < arr[i])
        {
            max = arr[i];
            idx = i;
        }
    }
    return idx;
}
 
// Function to return min_element index
static int min_element(int[] arr)
{
    int idx = 0;
    int min = arr[0];
    for(int i = 1; i < arr.length; i++)
    {
        if (arr[i] < min)
        {
            min = arr[i];
            idx = i;
        }
    }
    return idx;
}
 
// Driver Code
public static void main (String[] args)
{
    int arr[] = { 4, 1, 2, 3 };
    int n = arr.length;
     
    // Function call
    System.out.println(countSubArray(arr, n));
}
}
 
// This code is contributed by offbeat

# Python3 program for
# the above approach
 
# Function to count subarray
# containing both maximum and
# minimum array elements
def countSubArray(arr, n):
   
    # If the length of the
    # array is less than 2
    if (n < 2):
        return n;
 
    # Find the index of
    # maximum element
    i = max_element(arr);
 
    # Find the index of
    # minimum element
    j = min_element(arr);
 
    # If i > j, then swap
    # the value of i and j
    if (i > j):
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
 
    # Return the answer
    return (i + 1) * (n - j);
 
# Function to return
# max_element index
def max_element(arr):
    idx = 0;
    max = arr[0];
     
    for i in range(1, len(arr)):
        if (max < arr[i]):
            max = arr[i];
            idx = i;
    return idx;
 
# Function to return
# min_element index
def min_element(arr):
    idx = 0;
    min = arr[0];
     
    for i in range(1, len(arr)):
        if (arr[i] < min):
            min = arr[i];
            idx = i;
 
    return idx;
 
# Driver Code
if __name__ == '__main__':
    arr = [4, 1, 2, 3];
    n = len(arr);
 
    # Function call
    print(countSubArray(arr, n));
 
# This code is contributed by Rajput-Ji

// C# program for
// the above approach
using System;
class GFG{
     
// Function to count subarray
// containing both maximum and
// minimum array elements
static int countSubArray(int []arr,
                         int n)
{   
  // If the length of the
  // array is less than 2
  if (n < 2)
    return n;
 
  // Find the index of maximum element
  int i = max_element(arr);
 
  // Find the index of minimum element
  int j = min_element(arr);
 
  // If i > j, then swap
  // the value of i and j
  if (i > j)
  {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }
 
  // Return the answer
  return (i + 1) * (n - j);
}
 
// Function to return max_element index
static int max_element(int[] arr)
{
  int idx = 0;
  int max = arr[0];
  for(int i = 1; i < arr.Length; i++)
  {
    if(max < arr[i])
    {
      max = arr[i];
      idx = i;
    }
  }
  return idx;
}
 
// Function to return min_element index
static int min_element(int[] arr)
{
  int idx = 0;
  int min = arr[0];
  for(int i = 1; i < arr.Length; i++)
  {
    if (arr[i] < min)
    {
      min = arr[i];
      idx = i;
    }
  }
  return idx;
}
 
// Driver Code
public static void Main(String[] args)
{
  int []arr = {4, 1, 2, 3};
  int n = arr.Length;
 
  // Function call
  Console.WriteLine(countSubArray(arr, n));
}
}
 
// This code is contributed by shikhasingrajput

<script>
// javascript program for the
// above approach
 
// Function to count subarray
// containing both maximum and
// minimum array elements
function countSubArray(arr, n)
{
      
    // If the length of the
    // array is less than 2
    if (n < 2)
        return n;
  
    // Find the index of maximum element
    let i = max_element(arr);
  
    // Find the index of minimum element
    let j = min_element(arr);
  
    // If i > j, then swap
    // the value of i and j
    if (i > j)
    {
        let tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
          
    // Return the answer
    return (i + 1) * (n - j);
}
  
// Function to return max_element index
function max_element(arr)
{
    let idx = 0;
    let max = arr[0];
    for(let i = 1; i < arr.length; i++)
    {
        if(max < arr[i])
        {
            max = arr[i];
            idx = i;
        }
    }
    return idx;
}
  
// Function to return min_element index
function min_element(arr)
{
    let idx = 0;
    let min = arr[0];
    for(let i = 1; i < arr.length; i++)
    {
        if (arr[i] < min)
        {
            min = arr[i];
            idx = i;
        }
    }
    return idx;
}
  
// Driver Code
 
     let arr = [ 4, 1, 2, 3 ];
    let n = arr.length;
      
    // Function call
    document.write(countSubArray(arr, n));
  
 // This code is contributed by avijitmondal1998
</script>

3

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