Recuento de subarreglos con valor máximo como K

Dada una array arr[] de N enteros y un entero K . La tarea es encontrar el número de subarreglos con un valor máximo igual a K.

Ejemplos: 

Entrada: arr[ ] = {2, 1, 3, 4}, K = 3
Salida: 3
Explicación: 
Los sub-arreglos con valor máximo es igual a K son { 2, 1, 3 }, { 1, 3 }, { 3 }, por lo que la respuesta es 3.

Entrada: arr[ ] = {1, 2, 3}, K = 1.
Salida: 1

Enfoque: El número de subarreglos en el arreglo arr[] es igual al número de subarreglos con un máximo no mayor que K menos el número de subarreglos con un máximo no mayor que K-1. Consulte aquí para contar el número de subarreglos con un máximo mayor que K. Siga los pasos a continuación para resolver el problema:

• Inicialice la variable digamos, count1 como 0 para calcular el número de subarreglos con un máximo no mayor que K-1.
• Inicialice la variable digamos, count2 como 0 para calcular el número de subarreglos con un máximo no mayor que K.
• Defina una función , digamos, totalSubarrays(arr, N, K) para contar el número de subarreglos con un máximo no mayor que K y realice los siguientes pasos:
  • Inicialice la variable, digamos, ans como 0 para almacenar el recuento de subarreglos con un máximo no mayor que K.
  • Iterar en el rango [0, N-1] y realizar los siguientes pasos.
    • Si el valor de arr[i] es mayor que K, aumente el valor de i en 1 y continúe .
    • Inicialice la variable conteo como 0 para almacenar el conteo total de posibles subarreglos.
    • Iterar en el rango hasta que i sea menor que N y arr[i] sea menor que igual a K.
      • Aumenta el valor de i y cuenta de 1 en 1.
    • Sume el valor de (contar*(contar+1))/2 al valor de ans.
  • Devuelve el valor de ans.
• Calcule el número de subarreglos con un máximo no mayor que K-1 llamando a la función totalSubarrays(arr, N, K-1) y almacene en count1.
• Calcule el número de subarreglos con un máximo no mayor que K llamando a la función totalSubarrays(arr, N, K) y almacene en count2.
• Almacene el valor de (count2 – count1) en el valor final de ans e imprímalo.

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the subarrays with maximum
// not greater than K
int totalSubarrays(int arr[], int n, int k)
{
    int ans = 0, i = 0;
 
    while (i < n) {
        // If arr[i]>k then arr[i] cannot be
        // a part of any subarray.
        if (arr[i] > k) {
            i++;
            continue;
        }
 
        int count = 0;
        // Count the number of elements where
        // arr[i] is not greater than k.
        while (i < n && arr[i] <= k) {
            i++;
            count++;
        }
 
        // Summation of all possible subarrays
        // in the variable ans.
        ans += ((count * (count + 1)) / 2);
    }
 
    return ans;
}
 
// Function to count the subarrays with
// maximum value is equal to K
int countSubarrays(int arr[], int n, int k)
{
    // Stores count of subarrays with max <= k - 1.
    int count1 = totalSubarrays(arr, n, k - 1);
 
    // Stores count of subarrays with max >= k + 1.
    int count2 = totalSubarrays(arr, n, k);
 
    // Stores count of subarrays with max = k.
    int ans = count2 - count1;
 
    return ans;
}
 
// Driver Code
int main()
{
    // Given Input
    int n = 4, k = 3;
    int arr[] = { 2, 1, 3, 4 };
 
    // Function Call
    cout << countSubarrays(arr, n, k);
 
    return 0;
}

// Java program for the above approach
 
import java.io.*;
 
class GFG {
    // Function to count the subarrays with maximum
    // not greater than K
    static int totalSubarrays(int arr[], int n, int k)
    {
        int ans = 0, i = 0;
 
        while (i < n) {
            // If arr[i]>k then arr[i] cannot be
            // a part of any subarray.
            if (arr[i] > k) {
                i++;
                continue;
            }
 
            int count = 0;
            // Count the number of elements where
            // arr[i] is not greater than k.
            while (i < n && arr[i] <= k) {
                i++;
                count++;
            }
 
            // Summation of all possible subarrays
            // in the variable ans.
            ans += ((count * (count + 1)) / 2);
        }
 
        return ans;
    }
 
    // Function to count the subarrays with
    // maximum value is equal to K
    static int countSubarrays(int arr[], int n, int k)
    {
        // Stores count of subarrays with max <= k - 1.
        int count1 = totalSubarrays(arr, n, k - 1);
 
        // Stores count of subarrays with max >= k + 1.
        int count2 = totalSubarrays(arr, n, k);
 
        // Stores count of subarrays with max = k.
        int ans = count2 - count1;
 
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given Input
        int n = 4, k = 3;
        int arr[] = { 2, 1, 3, 4 };
 
        // Function Call
 
        System.out.println(countSubarrays(arr, n, k));
      // This code is contributed by Potta Lokesh
    }
}

# Python3 implementation of the above approach
 
# Function to count the subarrays with maximum
# not greater than K
def totalSubarrays(arr, n, k):
     
    ans = 0
    i = 0
 
    while (i < n):
         
        # If arr[i]>k then arr[i] cannot be
        # a part of any subarray.
        if (arr[i] > k):
            i += 1
            continue
 
        count = 0
         
        # Count the number of elements where
        # arr[i] is not greater than k.
        while (i < n and arr[i] <= k):
            i += 1
            count += 1
 
        # Summation of all possible subarrays
        # in the variable ans.
        ans += ((count * (count + 1)) // 2)
 
    return ans
 
# Function to count the subarrays with
# maximum value is equal to K
def countSubarrays(arr, n, k):
     
    # Stores count of subarrays with max <= k - 1.
    count1 = totalSubarrays(arr, n, k - 1)
 
    # Stores count of subarrays with max >= k + 1.
    count2 = totalSubarrays(arr, n, k)
 
    # Stores count of subarrays with max = k.
    ans = count2 - count1
 
    return ans
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    n = 4
    k = 3
    arr = [ 2, 1, 3, 4 ]
 
    # Function Call
    print(countSubarrays(arr, n, k))
 
# This code is contributed by ipg2016107

// C# program for the above approach
using System;
 
class GFG
{
    // Function to count the subarrays with maximum
    // not greater than K
    static int totalSubarrays(int[] arr, int n, int k)
    {
        int ans = 0, i = 0;
 
        while (i < n)
        {
           
            // If arr[i]>k then arr[i] cannot be
            // a part of any subarray.
            if (arr[i] > k) {
                i++;
                continue;
            }
 
            int count = 0;
           
            // Count the number of elements where
            // arr[i] is not greater than k.
            while (i < n && arr[i] <= k) {
                i++;
                count++;
            }
 
            // Summation of all possible subarrays
            // in the variable ans.
            ans += ((count * (count + 1)) / 2);
        }
 
        return ans;
    }
 
    // Function to count the subarrays with
    // maximum value is equal to K
    static int countSubarrays(int[] arr, int n, int k)
    {
        // Stores count of subarrays with max <= k - 1.
        int count1 = totalSubarrays(arr, n, k - 1);
 
        // Stores count of subarrays with max >= k + 1.
        int count2 = totalSubarrays(arr, n, k);
 
        // Stores count of subarrays with max = k.
        int ans = count2 - count1;
 
        return ans;
    }
    static void Main()
    {
        // Given Input
        int n = 4, k = 3;
        int[] arr = { 2, 1, 3, 4 };
 
        // Function Call
 
        Console.WriteLine(countSubarrays(arr, n, k));
    }
}
 
// This code is contributed by abhinavjain194

<script>
       // JavaScript program for the above approach
 
 
       // Function to count the subarrays with maximum
       // not greater than K
       function totalSubarrays(arr, n, k) {
           let ans = 0, i = 0;
 
           while (i < n) {
               // If arr[i]>k then arr[i] cannot be
               // a part of any subarray.
               if (arr[i] > k) {
                   i++;
                   continue;
               }
 
               let count = 0;
               // Count the number of elements where
               // arr[i] is not greater than k.
               while (i < n && arr[i] <= k) {
                   i++;
                   count++;
               }
 
               // Summation of all possible subarrays
               // in the variable ans.
               ans += (Math.floor((count * (count + 1)) / 2));
           }
 
           return ans;
       }
 
       // Function to count the subarrays with
       // maximum value is equal to K
       function countSubarrays(arr, n, k) {
           // Stores count of subarrays with max <= k - 1.
           let count1 = totalSubarrays(arr, n, k - 1);
 
           // Stores count of subarrays with max >= k + 1.
           let count2 = totalSubarrays(arr, n, k);
 
           // Stores count of subarrays with max = k.
           let ans = count2 - count1;
 
           return ans;
       }
 
       // Driver Code
 
       // Given Input
       let n = 4, k = 3;
       let arr = [2, 1, 3, 4];
 
       // Function Call
       document.write(countSubarrays(arr, n, k));
 
 
   // This code is contributed by Potta Lokesh
 
   </script>

3

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