Рубрики

Количество подмассивов с максимальными значениями в заданном диапазоне

Учитывая массив из N элементов и L и R, выведите количество подмассивов, чтобы значение максимального элемента массива в этом подмассиве было не менее L и не более R.

Примеры:

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} 

Наивным подходом будет итерация для каждого подмассива и поиск количества подмассивов с максимальным значением в диапазоне LR. Временная сложность этого решения составляет O (n * n)

Эффективный подход основан на следующих фактах:

  • Любой элемент> R никогда не включается ни в один подмассив.
  • Любое количество элементов, меньших L, может быть включено в подмассив, если между L и R включительно есть хотя бы один элемент.
  • Число всех возможных подмассивов массива размера N равно N * (N + 1) / 2. Пусть countSubarrays (N) = N * (N + 1) / 2

Мы отслеживаем два счета в текущем подмассиве.
1) Подсчет всех элементов, меньших или равных R. Мы называем это inc .
2) Подсчет всех элементов меньше L. Мы называем это исключением.

Наш ответ для текущего подмассива: countSubarrays (inc) — countSubarrays (exc). Мы в основном удаляем все те подмассивы, которые образованы только элементами меньше L.

Ниже приведена реализация вышеуказанного подхода.

C ++

// Программа CPP для подсчета подмассивов, чей максимум
// элементы находятся в заданном диапазоне.
#include <bits/stdc++.h>

using namespace std;

  
// функция для вычисления N * (N + 1) / 2

long countSubarrys(long n)

{

    return n * (n + 1) / 2;

}

  
// функция для подсчета количества подмассивов с
// максимум больше L и меньше R.

long countSubarrays(int a[], int n, int L, int R)

{

    long res = 0;

  

    // exc будет хранить количество элементов

    // меньше L в текущем действующем подмассиве.

    // inc собирается сохранить количество элементов

    // меньше или равно R.

    long exc = 0, inc = 0;

  

    // пройти через все элементы массива

    for (int i = 0; i < n; i++) {

  

        // Если элемент больше чем R,

        // добавить текущее значение в результат и сбросить

        // значения exc и inc.

        if (a[i] > R) {

            res += (countSubarrys(inc) - countSubarrys(exc));

            inc = 0;

            exc = 0;

        }

  

        // если оно меньше L, то оно включено

        // в подмассивах

        else if (a[i] < L) {

            exc++;

            inc++;

        }

  

        // если> = L и <= R, то счетчик

        // подмассивы, образованные предыдущим фрагментом

        // элементов, образованных только меньшими

        // элементы уменьшены из результата.

        else {

            res -= countSubarrys(exc);

            exc = 0;

            inc++;

        }

    }

  

    // Обновить результат.

    res += (countSubarrys(inc) - countSubarrys(exc));

  

    // возвращает количество вложенных массивов

    return res;

}

  
// драйверная программа

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-программа для подсчета подмассивов
// чьи максимальные элементы
// в заданном диапазоне.

  

class GFG {

      
// функция для вычисления N * (N + 1) / 2

static long countSubarrys(long n) 

{

    return n * (n + 1) / 2;

}

  
// функция для подсчета количества
// подмассивы с максимальным большим
// тогда L и меньше чем R.

static long countSubarrays(int a[], int n,

                             int L, int R) 

{

    long res = 0;

  

    // exc будет хранить количество элементов

    // меньше L в текущем действующем подмассиве.

    // inc собирается сохранить количество элементов

    // меньше или равно R.

    long exc = 0, inc = 0;

  

    // пройти через все элементы массива

    for (int i = 0; i < n; i++) {

  

    // Если элемент больше чем R,

    // добавить текущее значение в результат и сбросить

    // значения exc и inc.

    if (a[i] > R) {

        res += (countSubarrys(inc) - countSubarrys(exc));

        inc = 0;

        exc = 0;

    }

  

    // если оно меньше L, то оно включено

    // в подмассивах

    else if (a[i] < L) {

        exc++;

        inc++;

    }

  

    // если> = L и <= R, то счетчик

    // подмассивы, образованные предыдущим фрагментом

    // элементов, образованных только меньшими

    // элементы уменьшены из результата.

    else {

        res -= countSubarrys(exc);

        exc = 0;

        inc++;

    }

    }

  

    // Обновить результат.

    res += (countSubarrys(inc) - countSubarrys(exc));

  

    // возвращает количество вложенных массивов

    return res;

}

  
// Код драйвера

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));

}
}

  
// Этот код предоставлен Anant Agarwal.

python3

# Программа Python для подсчета
# подмассивы, чей максимум
# элементы находятся в заданном диапазоне.

  
# функция для расчета N * (N + 1) / 2

def countSubarrys(n):

  

    return n * (n + 1) // 2

  

   
# функция для подсчета
# количество подмассивов с
# максимум больше чем
# L и меньше чем R.

def countSubarrays(a,n,L,R):

  

    res = 0

   

    # exc собирается хранить

    # количество элементов

    # меньше, чем L в

    # текущий действующий подмассив.

    # inc собирается хранить

    # количество элементов

    # меньше или равно R.

    exc = 0

    inc = 0

   

    # пройти через все

    # элементы массива

    for i in range(n):

   

        # Если элемент

        # больше чем R,

        # добавить текущую стоимость

        # результат и сброс

        # значения exc и inc.

        if (a[i] > R):

              

            res =res + (countSubarrys(inc) - countSubarrys(exc))

            inc = 0

            exc = 0

          

   

        # если оно меньше L,

        # тогда это включено

        # в подмассивах

        elif (a[i] < L): 

            exc=exc + 1

            inc=inc + 1

          

   

        # если> = L и <= R, то количество

        # подмассивы, сформированные предыдущим фрагментом

        # элементов, образованных только меньшими

        # элементов уменьшается от результата.

        else

              

            res =res - countSubarrys(exc)

            exc = 0

            inc=inc + 1

   

    # Обновить результат.

    res =res + (countSubarrys(inc) - countSubarrys(exc))

   

    # возвращает количество подмассивов

    return res

      
# Код драйвера

  

a = [ 2, 0, 11, 3, 0]

n =len(a)

l = 1

r = 10

  

print(countSubarrays(a, n, l, r))

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # программа для подсчета подмассивов
// чьи максимальные элементы
// в заданном диапазоне.

using System;

  

class GFG 

{

      
// функция для
// вычисляем N * (N + 1) / 2

static long countSubarrys(long n) 

{

    return n * (n + 1) / 2;

}

  
// функция для подсчета
// количество подмассивов
// с максимальным большим
// тогда L и меньше чем R.

static long countSubarrays(int []a, int n,

                           int L, int R) 

{

    long res = 0;

  

    // exc собирается хранить

    // количество элементов меньше

    // чем L в текущем действительном

    // подмассив. Inc собирается

    // сохранить количество элементов

    // меньше или равно R.

    long exc = 0, inc = 0;

  

    // пройти через все

    // элементы массива

    for (int i = 0; i < n; i++)

    {

  

    // Если элемент больше

    // чем R, добавить текущее значение

    // выводить и сбрасывать значения

    // от и до

    if (a[i] > R) 

    {

        res += (countSubarrys(inc) - 

                countSubarrys(exc));

        inc = 0;

        exc = 0;

    }

  

    // если оно меньше L,

    // тогда он включен

    // в подмассивах

    else if (a[i] < L) 

    {

        exc++;

        inc++;

    }

  

    // если> = L и <= R, то

    // количество сформированных подмассивов

    // по предыдущему фрагменту элементов

    // сформирован только меньшими элементами

    // уменьшается от результата.

    else 

    {

        res -= countSubarrys(exc);

        exc = 0;

        inc++;

    }

    }

  

    // Обновить результат.

    res += (countSubarrys(inc) - 

            countSubarrys(exc));

  

    // возвращает счет

    // подмассивов

    return res;

}

  
// Код драйвера

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));

}
}

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP программа для подсчета подмассивов
// чьи максимальные элементы находятся в
// заданный диапазон.

  
// функция для вычисления N * (N + 1) / 2

function countSubarrys($n)

{

    return $n * ($n + 1) / 2;

}

  
// функция для подсчета числа
// подмассивов с максимумом
// больше L и меньше R.

function countSubarrays($a, $n

                        $L, $R)

{

    $res = 0;

  

    // exc собирается хранить

    // количество элементов меньше

    // чем L в текущем действительном

    // подмассив. Inc собирается

    // сохранить количество элементов

    // меньше или равно R.

    $exc = 0; $inc = 0;

  

    // пройти через все

    // элементы массива

    for ($i = 0; $i < $n; $i++)

    {

  

        // Если элемент больше

        // чем R, добавить текущее значение

        // выводить и сбрасывать значения

        // от и до

        if ($a[$i] > $R

        {

            $res += (countSubarrys($inc) - 

                     countSubarrys($exc));

            $inc = 0;

            $exc = 0;

        }

  

        // если оно меньше L,

        // тогда он включен

        // в подмассивах

        else if ($a[$i] < $L

        {

            $exc++;

            $inc++;

        }

  

        // если> = L и <= R, то

        // количество сформированных подмассивов

        // по предыдущему фрагменту элементов

        // сформирован только меньшими элементами

        // уменьшается от результата.

        else 

        {

            $res -= countSubarrys($exc);

            $exc = 0;

            $inc++;

        }

    }

  

    // Обновить результат.

    $res += (countSubarrys($inc) - 

             countSubarrys($exc));

  

    // возвращает счет

    // подмассивов

    return $res;

}

  
// Код драйвера

$a = array(2, 0, 11, 3, 0 );

$n = count($a);

$l = 1; $r = 10;

echo countSubarrays($a, $n, $l, $r);

  
// Этот код добавлен
// от anuj_67.
?>


Выход:

4

Сложность времени: O (n)

Рекомендуемые посты:

Количество подмассивов с максимальными значениями в заданном диапазоне

0.00 (0%) 0 votes