Recuento de subarreglos cuyo elemento máximo es mayor que k

Dado un arreglo de n elementos y un entero k . La tarea es encontrar el conteo del subarreglo que tiene un elemento máximo mayor que K.

Ejemplos: 

Input : arr[] = {1, 2, 3} and k = 2.
Output : 3
All the possible subarrays of arr[] are 
{ 1 }, { 2 }, { 3 }, { 1, 2 }, { 2, 3 }, 
{ 1, 2, 3 }.
Their maximum elements are 1, 2, 3, 2, 3, 3.
There are only 3 maximum elements > 2.

La idea es abordar el problema contando los subarreglos cuyo elemento máximo es menor o igual que k, ya que contar tales subarreglos es más fácil. Para encontrar el número de subarreglo cuyo elemento máximo es menor o igual a k, elimine todo el elemento que sea mayor que K y encuentre el número de subarreglo con los elementos de la izquierda. 

Una vez que encontramos el conteo anterior, podemos restarlo de n*(n+1)/2 para obtener el resultado requerido. Observe, puede haber n*(n+1)/2 número posible de subarreglo de cualquier arreglo de tamaño n. Entonces, encontrar el número de subarreglo cuyo elemento máximo es menor o igual a K y restarlo de n*(n+1)/2 nos da la respuesta.

A continuación se muestra la implementación de este enfoque:

// C++ program to count number of subarrays
// whose maximum element is greater than K.
#include <bits/stdc++.h>
using namespace std;
 
// Return number of subarrays whose maximum
// element is less than or equal to K.
int countSubarray(int arr[], int n, int k)
{
    // To store count of subarrays with all
    // elements less than or equal to k.
    int s = 0;
 
    // Traversing the array.
    int i = 0;
    while (i < n) {
        // If element is greater than k, ignore.
        if (arr[i] > k) {
            i++;
            continue;
        }
 
        // Counting the subarray length whose
        // each element is less than equal to k.
        int count = 0;
        while (i < n && arr[i] <= k) {
            i++;
            count++;
        }
 
        // Summing number of subarray whose
        // maximum element is less than equal to k.
        s += ((count * (count + 1)) / 2);
    }
 
    return (n * (n + 1) / 2 - s);
}
 
// Driven Program
int main()
{
    int arr[] = { 1, 2, 3 };
    int k = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << countSubarray(arr, n, k);
    return 0;
}

// Java program to count number of subarrays
// whose maximum element is greater than K.
import java.util.*;
 
class GFG {
 
    // Return number of subarrays whose maximum
    // element is less than or equal to K.
    static int countSubarray(int arr[], int n, int k)
    {
 
        // To store count of subarrays with all
        // elements less than or equal to k.
        int s = 0;
 
        // Traversing the array.
        int i = 0;
        while (i < n) {
 
            // If element is greater than k, ignore.
            if (arr[i] > k) {
                i++;
                continue;
            }
 
            // Counting the subarray length whose
            // each element is less than equal to k.
            int count = 0;
            while (i < n && arr[i] <= k) {
                i++;
                count++;
            }
 
            // Summing number of subarray whose
            // maximum element is less than equal to k.
            s += ((count * (count + 1)) / 2);
        }
 
        return (n * (n + 1) / 2 - s);
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        int arr[] = { 1, 2, 3 };
        int k = 2;
        int n = arr.length;
        System.out.print(countSubarray(arr, n, k));
    }
}
 
// This code is contributed by Anant Agarwal.

# Python program to count
# number of subarrays
# whose maximum element
# is greater than K.
 
# Return number of
# subarrays whose maximum
# element is less than or equal to K.
def countSubarray(arr, n, k):
 
    # To store count of
    # subarrays with all
    # elements less than
    # or equal to k.
    s = 0
  
    # Traversing the array.
    i = 0
    while (i < n):
     
        # If element is greater
        # than k, ignore.
        if (arr[i] > k):
         
            i = i + 1
            continue
         
        # Counting the subarray
        # length whose
        # each element is less
        # than equal to k.
        count = 0
        while (i < n and arr[i] <= k):
         
            i = i + 1
            count = count + 1
         
  
        # Summing number of subarray whose
        # maximum element is less
        # than equal to k.
        s = s + ((count*(count + 1))//2)
     
  
    return (n*(n + 1)//2 - s)
     
# Driver code
 
arr = [1, 2, 3]
k = 2
n = len(arr)
 
print(countSubarray(arr, n, k))
 
# This code is contributed
# by Anant Agarwal.

// C# program to count number of subarrays
// whose maximum element is greater than K.
using System;
 
class GFG {
 
    // Return number of subarrays whose maximum
    // element is less than or equal to K.
    static int countSubarray(int[] arr, int n, int k)
    {
        // To store count of subarrays with all
        // elements less than or equal to k.
        int s = 0;
 
        // Traversing the array.
        int i = 0;
        while (i < n) {
 
            // If element is greater than k, ignore.
            if (arr[i] > k) {
                i++;
                continue;
            }
 
            // Counting the subarray length whose
            // each element is less than equal to k.
            int count = 0;
            while (i < n && arr[i] <= k) {
                i++;
                count++;
            }
 
            // Summing number of subarray whose
            // maximum element is less than equal to k.
            s += ((count * (count + 1)) / 2);
        }
 
        return (n * (n + 1) / 2 - s);
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = {1, 2, 3};
        int k = 2;
        int n = arr.Length;
        Console.WriteLine(countSubarray(arr, n, k));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to count number of subarrays
// whose maximum element is greater than K.
 
// Return number of subarrays whose maximum
// element is less than or equal to K.
function countSubarray( $arr, $n, $k)
{
     
    // To store count of subarrays with all
    // elements less than or equal to k.
    $s = 0;
 
    // Traversing the array.
    $i = 0;
    while ($i < $n) {
         
        // If element is greater than k,
        // ignore.
        if ($arr[$i] > $k) {
            $i++;
            continue;
        }
 
        // Counting the subarray length
        // whose each element is less
        // than equal to k.
        $count = 0;
        while ($i < $n and $arr[$i] <= $k) {
            $i++;
            $count++;
        }
 
        // Summing number of subarray whose
        // maximum element is less than
        // equal to k.
        $s += (($count * ($count + 1)) / 2);
    }
 
    return ($n * ($n + 1) / 2 - $s);
}
 
// Driven Program
    $arr = array( 1, 2, 3 );
    $k = 2;
    $n = count($arr);
    echo countSubarray($arr, $n, $k);
 
// This code is contributed by anuj_67.
?>

<script>
    // Javascript program to count number of subarrays
    // whose maximum element is greater than K.
     
    // Return number of subarrays whose maximum
    // element is less than or equal to K.
    function countSubarray(arr, n, k)
    {
        // To store count of subarrays with all
        // elements less than or equal to k.
        let s = 0;
   
        // Traversing the array.
        let i = 0;
        while (i < n) {
   
            // If element is greater than k, ignore.
            if (arr[i] > k) {
                i++;
                continue;
            }
   
            // Counting the subarray length whose
            // each element is less than equal to k.
            let count = 0;
            while (i < n && arr[i] <= k) {
                i++;
                count++;
            }
   
            // Summing number of subarray whose
            // maximum element is less than equal to k.
            s += parseInt((count * (count + 1)) / 2, 10);
        }
   
        return (n * parseInt((n + 1) / 2, 10) - s);
    }
     
    let arr = [1, 2, 3];
    let k = 2;
    let n = arr.length;
    document.write(countSubarray(arr, n, k));
     
</script>

3

Complejidad temporal: O(n).
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.