Número de subarreglos con valores máximos en un rango dado

Posted on by Rudeus Greyrat

Dada una array de N elementos y L y R, imprima el número de subarreglos de modo que el valor del elemento de array máximo en ese subarreglo sea al menos L y como máximo R. 

Ejemplos:  

Input : arr[] = {2, 0, 11, 3, 0}
          L = 1, R = 10
Output : 4 
Explanation: the sub-arrays {2}, {2, 0}, {3} 
and {3, 0} have maximum in range 1-10.

Input : arr[] = {3, 4, 1}
          L = 2, R = 4 
Output : 5
Explanation: the sub-arrays are {3}, {4}, 
{3, 4}, {4, 1} and {3, 4, 1}

Un enfoque ingenuo será iterar para cada subarreglo y encontrar el número de subarreglos con el máximo en el rango LR. La complejidad temporal de esta solución es O(n*n) .

Un enfoque eficiente se basa en los siguientes hechos:  

  • Cualquier elemento > R nunca se incluye en ningún subarreglo.
  • Cualquier número de elementos más pequeños que L puede incluirse en un subarreglo siempre que haya al menos un solo elemento entre L y R inclusive.
  • El número de todos los subarreglos posibles de un arreglo de tamaño N es N * (N + 1)/2. Sea countSubarrays(N) = N * (N + 1)/2

Realizamos un seguimiento de dos recuentos en el subarreglo actual. 

  1. Recuento de todos los elementos menores o iguales a R. Lo llamamos inc . 
  2. Recuento de todos los elementos menores que L. Lo llamamos exc.

Nuestra respuesta para el subarreglo actual es countSubarrays(inc) – countSubarrays(exc). Básicamente, eliminamos todos aquellos subarreglos que están formados solo por elementos más pequeños que L.

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

C++

// CPP program to count subarrays whose maximum
// elements are in given range.
#include <bits/stdc++.h>
using namespace std;
 
// function to calculate N*(N+1)/2
long countSubarrys(long n)
{
    return n * (n + 1) / 2;
}
 
// function to count the number of sub-arrays with
// maximum greater then L and less then R.
long countSubarrays(int a[], int n, int L, int R)
{
    long res = 0;
 
    // exc is going to store count of elements
    // smaller than L in current valid subarray.
    // inc is going to store count of elements
    // smaller than or equal to R.
    long exc = 0, inc = 0;
 
    // traverse through all elements of the array
    for (int i = 0; i < n; i++) {
 
        // If the element is greater than R,
        // add current value to result and reset
        // values of exc and inc.
        if (a[i] > R) {
            res += (countSubarrys(inc) - countSubarrys(exc));
            inc = 0;
            exc = 0;
        }
 
        // if it is less than L, then it is included
        // in the sub-arrays
        else if (a[i] < L) {
            exc++;
            inc++;
        }
 
        // if >= L and <= R, then count of
        // subarrays formed by previous chunk
        // of elements formed by only smaller
        // elements is reduced from result.
        else {
            res -= countSubarrys(exc);
            exc = 0;
            inc++;
        }
    }
 
    // Update result.
    res += (countSubarrys(inc) - countSubarrys(exc));
 
    // returns the count of sub-arrays
    return res;
}
 
// driver program
int main()
{
    int a[] = { 2, 0, 11, 3, 0 };
    int n = sizeof(a) / sizeof(a[0]);
    int l = 1, r = 10;
    cout << countSubarrays(a, n, l, r);
    return 0;
}

Java

// Java program to count subarrays
// whose maximum elements are
// in given range.
 
class GFG {
     
// function to calculate N*(N+1)/2
static long countSubarrys(long n)
{
    return n * (n + 1) / 2;
}
 
// function to count the number of
// sub-arrays with maximum greater
// then L and less then R.
static long countSubarrays(int a[], int n,
                             int L, int R)
{
    long res = 0;
 
    // exc is going to store count of elements
    // smaller than L in current valid subarray.
    // inc is going to store count of elements
    // smaller than or equal to R.
    long exc = 0, inc = 0;
 
    // traverse through all elements of the array
    for (int i = 0; i < n; i++) {
 
    // If the element is greater than R,
    // add current value to result and reset
    // values of exc and inc.
    if (a[i] > R) {
        res += (countSubarrys(inc) - countSubarrys(exc));
        inc = 0;
        exc = 0;
    }
 
    // if it is less than L, then it is included
    // in the sub-arrays
    else if (a[i] < L) {
        exc++;
        inc++;
    }
 
    // if >= L and <= R, then count of
    // subarrays formed by previous chunk
    // of elements formed by only smaller
    // elements is reduced from result.
    else {
        res -= countSubarrys(exc);
        exc = 0;
        inc++;
    }
    }
 
    // Update result.
    res += (countSubarrys(inc) - countSubarrys(exc));
 
    // returns the count of sub-arrays
    return res;
}
 
// Driver code
public static void main(String arg[])
{
    int a[] = {2, 0, 11, 3, 0};
    int n = a.length;
    int l = 1, r = 10;
    System.out.print(countSubarrays(a, n, l, r));
}
}
 
// This code is contributed by Anant Agarwal.

Python3

# Python program to count
# subarrays whose maximum
# elements are in given range.
 
# function to calculate N*(N+1)/2
def countSubarrys(n):
 
    return n * (n + 1) // 2
 
  
# function to count the
# number of sub-arrays with
# maximum greater then
# L and less then R.
def countSubarrays(a,n,L,R):
 
    res = 0
  
    # exc is going to store
    # count of elements
    # smaller than L in
    # current valid subarray.
    # inc is going to store
    # count of elements
    # smaller than or equal to R.
    exc = 0
    inc = 0
  
    # traverse through all
    # elements of the array
    for i in range(n):
  
        # If the element is
        # greater than R,
        # add current value
        # to result and reset
        # values of exc and inc.
        if (a[i] > R):
             
            res =res + (countSubarrys(inc) - countSubarrys(exc))
            inc = 0
            exc = 0
         
  
        # if it is less than L,
        # then it is included
        # in the sub-arrays
        elif (a[i] < L):
            exc=exc + 1
            inc=inc + 1
         
  
        # if >= L and <= R, then count of
        # subarrays formed by previous chunk
        # of elements formed by only smaller
        # elements is reduced from result.
        else:
             
            res =res - countSubarrys(exc)
            exc = 0
            inc=inc + 1
  
    # Update result.
    res =res + (countSubarrys(inc) - countSubarrys(exc))
  
    # returns the count of sub-arrays
    return res
     
# Driver code
 
a = [ 2, 0, 11, 3, 0]
n =len(a)
l = 1
r = 10
 
print(countSubarrays(a, n, l, r))
 
# This code is contributed
# by Anant Agarwal.

C#

// C# program to count subarrays
// whose maximum elements are
// in given range.
using System;
 
class GFG
{
     
// function to
// calculate N*(N+1)/2
static long countSubarrys(long n)
{
    return n * (n + 1) / 2;
}
 
// function to count the
// number of sub-arrays
// with maximum greater
// then L and less then R.
static long countSubarrays(int []a, int n,
                           int L, int R)
{
    long res = 0;
 
    // exc is going to store
    // count of elements smaller
    // than L in current valid
    // subarray. inc is going to
    // store count of elements
    // smaller than or equal to R.
    long exc = 0, inc = 0;
 
    // traverse through all
    // elements of the array
    for (int i = 0; i < n; i++)
    {
 
    // If the element is greater
    // than R, add current value
    // to result and reset values
    // of exc and inc.
    if (a[i] > R)
    {
        res += (countSubarrys(inc) -
                countSubarrys(exc));
        inc = 0;
        exc = 0;
    }
 
    // if it is less than L,
    // then it is included
    // in the sub-arrays
    else if (a[i] < L)
    {
        exc++;
        inc++;
    }
 
    // if >= L and <= R, then
    // count of subarrays formed
    // by previous chunk of elements
    // formed by only smaller elements
    // is reduced from result.
    else
    {
        res -= countSubarrys(exc);
        exc = 0;
        inc++;
    }
    }
 
    // Update result.
    res += (countSubarrys(inc) -
            countSubarrys(exc));
 
    // returns the count
    // of sub-arrays
    return res;
}
 
// Driver code
public static void Main()
{
    int []a = {2, 0, 11, 3, 0};
    int n = a.Length;
    int l = 1, r = 10;
    Console.WriteLine(countSubarrays(a, n,
                                     l, r));
}
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to count subarrays
// whose maximum elements are in
// given range.
 
// function to calculate N*(N+1)/2
function countSubarrys($n)
{
    return $n * ($n + 1) / 2;
}
 
// function to count the number
// of sub-arrays with maximum
// greater then L and less then R.
function countSubarrays($a, $n,
                        $L, $R)
{
    $res = 0;
 
    // exc is going to store
    // count of elements smaller
    // than L in current valid
    // subarray. inc is going to
    // store count of elements
    // smaller than or equal to R.
    $exc = 0; $inc = 0;
 
    // traverse through all
    // elements of the array
    for ($i = 0; $i < $n; $i++)
    {
 
        // If the element is greater
        // than R, add current value
        // to result and reset values
        // of exc and inc.
        if ($a[$i] > $R)
        {
            $res += (countSubarrys($inc) -
                     countSubarrys($exc));
            $inc = 0;
            $exc = 0;
        }
 
        // if it is less than L,
        // then it is included
        // in the sub-arrays
        else if ($a[$i] < $L)
        {
            $exc++;
            $inc++;
        }
 
        // if >= L and <= R, then
        // count of subarrays formed
        // by previous chunk of elements
        // formed by only smaller elements
        // is reduced from result.
        else
        {
            $res -= countSubarrys($exc);
            $exc = 0;
            $inc++;
        }
    }
 
    // Update result.
    $res += (countSubarrys($inc) -
             countSubarrys($exc));
 
    // returns the count
    // of sub-arrays
    return $res;
}
 
// Driver Code
$a = array(2, 0, 11, 3, 0 );
$n = count($a);
$l = 1; $r = 10;
echo countSubarrays($a, $n, $l, $r);
 
// This code is contributed
// by anuj_67.
?>

Javascript

<script>
// javascript program to count subarrays
// whose maximum elements are
// in given range.
    // function to calculate N*(N+1)/2
    function countSubarrys(n) {
        return n * (n + 1) / 2;
    }
 
    // function to count the number of
    // sub-arrays with maximum greater
    // then L and less then R.
    function countSubarrays(a , n , L , R) {
        var res = 0;
 
        // exc is going to store count of elements
        // smaller than L in current valid subarray.
        // inc is going to store count of elements
        // smaller than or equal to R.
        var exc = 0, inc = 0;
 
        // traverse through all elements of the array
        for (i = 0; i < n; i++) {
 
            // If the element is greater than R,
            // add current value to result and reset
            // values of exc and inc.
            if (a[i] > R) {
                res += (countSubarrys(inc) - countSubarrys(exc));
                inc = 0;
                exc = 0;
            }
 
            // if it is less than L, then it is included
            // in the sub-arrays
            else if (a[i] < L) {
                exc++;
                inc++;
            }
 
            // if >= L and <= R, then count of
            // subarrays formed by previous chunk
            // of elements formed by only smaller
            // elements is reduced from result.
            else {
                res -= countSubarrys(exc);
                exc = 0;
                inc++;
            }
        }
 
        // Update result.
        res += (countSubarrys(inc) - countSubarrys(exc));
 
        // returns the count of sub-arrays
        return res;
    }
 
    // Driver code
        var a = [ 2, 0, 11, 3, 0 ];
        var n = a.length;
        var l = 1, r = 10;
        document.write(countSubarrays(a, n, l, r));
 
// This code is contributed by todaysgaurav
</script>

Producción:  

4

Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.

Publicación traducida automáticamente

Artículo escrito por Striver 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 *