Рубрики

Количество подмассивов, максимальный элемент которых больше k

Дан массив из n элементов и целое число k . Задача состоит в том, чтобы найти число подмассивов, у которых максимальный элемент больше K.

Примеры :

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.

Идея состоит в том, чтобы приблизиться к проблеме путем подсчета подмассивов, чей максимальный элемент меньше или равен k, поскольку подсчет таких подмассивов проще. Чтобы найти номер подмассива, максимальный элемент которого меньше или равен k, удалите все элементы, которые больше K, и найдите номер подмассива с левыми элементами.
Как только мы найдем число выше, мы можем вычесть его из n * (n + 1) / 2, чтобы получить требуемый результат. Заметьте, что может быть n * (n + 1) / 2 возможного числа подмассива любого массива размера n. Таким образом, нахождение числа подмассива, максимальный элемент которого меньше или равен K, и вычитание его из n * (n + 1) / 2 дает нам ответ.

Ниже приведена реализация этого подхода:

C ++

// C ++ программа для подсчета количества подмассивов
// чей максимальный элемент больше K.
#include <bits/stdc++.h>

using namespace std;

  
// Возвращаем количество подмассивов, чей максимум
// элемент меньше или равен K.

int countSubarray(int arr[], int n, int k)

{

    // Хранить количество подмассивов со всеми

    // элементы, меньшие или равные k.

    int s = 0;

  

    // Обход массива.

    int i = 0;

    while (i < n) {

        // Если элемент больше k, игнорировать.

        if (arr[i] > k) {

            i++;

            continue;

        }

  

        // Подсчитываем длину подмассива которого

        // каждый элемент меньше чем равен k.

        int count = 0;

        while (i < n && arr[i] <= k) {

            i++;

            count++;

        }

  

        // Суммируем номер подмассива, у которого

        // максимальный элемент меньше чем равен k.

        s += ((count * (count + 1)) / 2);

    }

  

    return (n * (n + 1) / 2 - s);

}

  
// Управляемая программа

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

import java.util.*;

  

class GFG {

  

    // Возвращаем количество подмассивов, чей максимум

    // элемент меньше или равен K.

    static int countSubarray(int arr[], int n, int k)

    {

  

        // Хранить количество подмассивов со всеми

        // элементы, меньшие или равные k.

        int s = 0;

  

        // Обход массива.

        int i = 0;

        while (i < n) {

  

            // Если элемент больше k, игнорировать.

            if (arr[i] > k) {

                i++;

                continue;

            }

  

            // Подсчитываем длину подмассива которого

            // каждый элемент меньше чем равен k.

            int count = 0;

            while (i < n && arr[i] <= k) {

                i++;

                count++;

            }

  

            // Суммируем номер подмассива, у которого

            // максимальный элемент меньше чем равен k.

            s += ((count * (count + 1)) / 2);

        }

  

        return (n * (n + 1) / 2 - s);

    }

  

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

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

    }

}

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

python3

# Программа Python для подсчета
# количество подмассивов
# чей максимальный элемент
# больше К.

  
# Возвращаемое количество
# подмассивы, чей максимум
# элемент меньше или равен K.

def countSubarray(arr, n, k):

  

    # Хранить количество

    # подрешетки со всеми

    # элементов меньше чем

    # или равно k.

    s = 0

   

    # Обход массива.

    i = 0

    while (i < n):

      

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

        # чем, игнорируй.

        if (arr[i] > k):

          

            i = i + 1

            continue

          

        # Подсчет подмассива

        # длина которого

        # каждый элемент меньше

        # чем равно k.

        count = 0

        while (i < n and arr[i] <= k):

          

            i = i + 1

            count = count + 1

          

   

        # Суммирование номера подмассива которого

        # максимальный элемент меньше

        # чем равно k.

        s = s + ((count*(count + 1))//2)

      

   

    return (n*(n + 1)//2 - s)

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

  

arr = [1, 2, 3]

k = 2

n = len(arr)

  

print(countSubarray(arr, n, k))

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

C #

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

using System;

  

class GFG {

  

    // Возвращаем количество подмассивов, чей максимум

    // элемент меньше или равен K.

    static int countSubarray(int[] arr, int n, int k)

    {

        // Хранить количество подмассивов со всеми

        // элементы, меньшие или равные k.

        int s = 0;

  

        // Обход массива.

        int i = 0;

        while (i < n) {

  

            // Если элемент больше k, игнорировать.

            if (arr[i] > k) {

                i++;

                continue;

            }

  

            // Подсчитываем длину подмассива которого

            // каждый элемент меньше чем равен k.

            int count = 0;

            while (i < n && arr[i] <= k) {

                i++;

                count++;

            }

  

            // Суммируем номер подмассива, у которого

            // максимальный элемент меньше чем равен k.

            s += ((count * (count + 1)) / 2);

        }

  

        return (n * (n + 1) / 2 - s);

    }

  

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

    public static void Main()

    {

        int[] arr = {1, 2, 3};

        int k = 2;

        int n = arr.Length;

        Console.WriteLine(countSubarray(arr, n, k));

    }

}

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

PHP

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

  
// Возвращаем количество подмассивов, чей максимум
// элемент меньше или равен K.

function countSubarray( $arr, $n, $k)

{

      

    // Хранить количество подмассивов со всеми

    // элементы, меньшие или равные k.

    $s = 0;

  

    // Обход массива.

    $i = 0;

    while ($i < $n) {

          

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

        // игнорировать

        if ($arr[$i] > $k) {

            $i++;

            continue;

        }

  

        // Подсчитываем длину подмассива

        // каждый элемент которого меньше

        // чем равно k.

        $count = 0;

        while ($i < $n and $arr[$i] <= $k) {

            $i++;

            $count++;

        }

  

        // Суммируем номер подмассива, у которого

        // максимальный элемент меньше чем

        // равно k.

        $s += (($count * ($count + 1)) / 2);

    }

  

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

}

  
// Управляемая программа

    $arr = array( 1, 2, 3 );

    $k = 2;

    $n = count($arr);

    echo countSubarray($arr, $n, $k);

  
// Этот код предоставлен anuj_67.
?>


Выход:

3

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

Эта статья предоставлена Anuj Chauhan . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Количество подмассивов, максимальный элемент которых больше k

0.00 (0%) 0 votes