logo

TechCodeview

Брой подмасиви, чийто максимален елемент е по-голям от 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.
Recommended Practice Брой подмасиви Опитайте!

Подход 1: Преброяване на подмасиви с максимален елемент<= K and then subtracting from total subarrays.

Идеята е да се подходи към проблема чрез преброяване на подмасиви, чийто максимален елемент е по-малък или равен на k, тъй като преброяването на такива подмасиви е по-лесно. За да намерите броя на подмасива, чийто максимален елемент е по-малък или равен на k, премахнете всички елементи, които са по-големи от K, и намерете броя на подмасива с левите елементи. 



След като намерим горния брой, можем да го извадим от n*(n+1)/2, за да получим желания резултат. Забележете, че може да има n*(n+1)/2 възможен брой подмасиви от всеки масив с размер n. Така че намирането на броя на подмасива, чийто максимален елемент е по-малък или равен на K и изваждането му от n*(n+1)/2 ни дава отговора.

По-долу е изпълнението на този подход:

C++ 
// C++ program to count number of subarrays // whose maximum element is greater than K. #include    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 
// 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.
Python3 
# 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# 
// 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.
JavaScript 
<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>
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. ?>

Изход 
3

Времева сложност: O(n).
Помощно пространство: O(1)

Подход 2: Преброяване на подмасиви с максимален елемент > K

При този подход ние просто намираме броя на подмасивите, които могат да бъдат формирани чрез включване на елемент с индекс i, който е по-голям от K. Следователно, ако приемем arr [ i ] > K тогава всички подмасиви, в които присъства този елемент, ще имат стойност, която е по-голяма от k, така че ние просто изчисляваме всички тези подмасиви за всеки елемент, който е по-голям от K, и ги добавяме в отговор. Първо инициализираме две променливи години = 0 това съдържа отговор и предишна = -1 това следи индекса на предишния елемент, който е бил по-голям от K.

За да направим това, имаме нужда от три стойности за всеки arr [ i ] > K .

  1. Брой подмасиви, започващи от индекса аз . Това ще бъде ( N - i ) . ЗАБЕЛЕЖКА: Тук сме включили подмасива, съдържащ един елемент, който е самият този елемент. { arr [ i ] }
  2. Брой подмасиви, завършващи на този индекс i но началният индекс на тези подмасиви е след индекса предишна на предишен елемент, който е бил по-голям от K защо правим това? Тъй като за тези елементи трябва вече да сме изчислили нашия отговор, така че не искаме да броим едни и същи подмасиви повече от веднъж. Така че тази стойност ще се появи ( i - предишна - 1 ) . ЗАБЕЛЕЖКА: Тук изваждаме 1, защото вече сме преброили подмасив { arr [ i ] }, който има себе си като единичен елемент. Вижте бележката по-горе. 
  3. Брой подмасиви с начален индекс по-малък от аз но по-голямо от предишна и краен индекс по-голям от аз . Следователно всички подмасиви, в които arr[i] е между тях. Това можем да изчислим, като умножим горните две стойности. Да ги кажем като L = ( N - i - 1 ) и R = ( i - предишна -1 ). Сега просто умножаваме тези L и R, защото за всеки 1 индекс от лявата страна на i има R индекс, който може да направи различни подмасиви основни математически неща. Така че това става L * R . Забележете, че тук във val на L ние всъщност сме извадили 1, ако не направим това, тогава включваме индекс i в нашия L*R, което ще означава, че отново сме включили подмасиви от тип номер 1. Вижте точка 1.    

По-долу е изпълнението на този подход:

C++ 
// C++ program to count number of subarrays // whose maximum element is greater than K. #include    using namespace std; long long countSubarray(int arr[] int n int k) {  long long ans = 0 ;  int prev = - 1; //prev for keeping track of index of previous element > k;  for(int i = 0 ; i < n ; i++ ) {  if ( arr [ i ] > k ) {  ans += n - i ; //subarrays starting at index i.  ans += i - prev - 1 ; //subarrays ending at index i but starting after prev.  ans += ( n - i - 1 ) * 1LL * ( i - prev - 1 ) ; //subarrays having index i element in between.  prev = i; // updating prev  }  }  return ans; } // Driven Program int main() {  int arr[] = { 4 5 1 2 3 };  int k = 2;  int n = sizeof(arr) / sizeof(arr[0]);  cout << countSubarray(arr n k);  return 0; } // This Code is contributed by Manjeet Singh.
Java 
// Java program to count number of subarrays // whose maximum element is greater than K. import java.util.*; public class GFG {  static long countSubarray(int arr[] int n int k)  {  long ans = 0 ;  int prev = - 1; //prev for keeping track of index of previous element > k;  for(int i = 0 ; i < n ; i++ ) {  if ( arr [ i ] > k ) {  ans += n - i ; //subarrays starting at index i.  ans += i - prev - 1 ; //subarrays ending at index i but starting after prev.  ans += ( n - i - 1 ) * 1L * ( i - prev - 1 ) ; //subarrays having index i element in between.  prev = i; // updating prev  }  }  return ans;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 4 5 1 2 3 };  int k = 2;  int n = arr.length;  System.out.print(countSubarray(arr n k));  } } //This Code is contributed by Manjeet Singh
Python3 
# Python program to count number of subarrays # whose maximum element is greater than K. def countSubarray( arr n k): ans = 0 ; prev = - 1; #prev for keeping track of index of previous element > k; for i in range(0n): if ( arr [ i ] > k ) : ans += n - i ; #subarrays starting at index i. ans += i - prev - 1 ; #subarrays ending at index i but starting after prev. ans += ( n - i - 1 ) * ( i - prev - 1 ) ; #subarrays having index i element in between. prev = i; # updating prev return ans; # Driven Program arr = [ 4 5 1 2 3 ]; k = 2; n = len(arr); print(countSubarray(arr n k)); # this code is contributed by poojaagarwal2.
C# 
// C# program to count number of subarrays // whose maximum element is greater than K. using System; public class GFG {  static long countSubarray(int[] arr int n int k)  {  long ans = 0;  int prev = -1; // prev for keeping track of index of  // previous element > k;  for (int i = 0; i < n; i++) {  if (arr[i] > k) {  ans += n - i; // subarrays starting at index  // i.  ans += i - prev  - 1; // subarrays ending at index i  // but starting after prev.  ans += (n - i - 1) * (long)1  * (i - prev  - 1); // subarrays having index i  // element in between.  prev = i; // updating prev  }  }  return ans;  }  // Driver code  public static void Main(string[] args)  {  int[] arr = { 4 5 1 2 3 };  int k = 2;  int n = arr.Length;  Console.Write(countSubarray(arr n k));  } } // This Code is contributed by Karandeep1234
JavaScript 
// Javascript program to count number of subarrays // whose maximum element is greater than K. function countSubarray(arr n k) {  let ans = 0 ;  //prev for keeping track of index of previous element > k;  let prev = - 1;   for(let i = 0 ; i < n ; i++ ) {  if ( arr [ i ] > k ) {  //subarrays starting at index i.  ans += n - i ;   //subarrays ending at index i but starting after prev.  ans += i - prev - 1 ;  //subarrays having index i element in between.  ans += ( n - i - 1 ) * 1 * ( i - prev - 1 ) ;   // updating prev  prev = i;   }  }  return ans; } // Driven Program  let arr = [ 4 5 1 2 3 ];  let k = 2;  let n = arr.length;  document.write(countSubarray(arr n k));

Изход 
12

Времева сложност: O(n).

Подход 3: Техника на плъзгащ се прозорец.

Алгоритъм:

1. Инициализирайте променлива години = 0 променлива maxElement = 0 и променлива брой = 0 .

2. Итерирайте през масива, като правите следното за всеки елемент:

  а. Ако текущият елемент, т.е. пристигам [ аз ] е по-голямо от текущия максимум, актуализирайте максимума, т.е. Радиото = arr ] и нулирайте брояча на 0.

  b. Ако текущият елемент е по-малък или равен на текущия максимум, увеличете броя.

  c. Ако maxElement тогава е grteater от k добавяне на брой от подмасиви до окончателен отговор и актуализиране на maxElement към текущия елемент.

3. Връщане Окончателен отговор.

Ето изпълнението на техниката на плъзгащия се прозорец.

C++ 
#include    using namespace std; int countSubarray(int arr[] int n int k) {  int maxElement = 0 count = 0 ans = 0;  for(int i=0; i<n; i++) {  if(arr[i] > maxElement) {  maxElement = arr[i];  count = 0;  }  else {  count++;  }  if(maxElement > k) {  ans += (i - count + 1);  maxElement = arr[i];  count = 0;  }  }  return ans; } int main() {  int arr[] = {1 2 3 4};  int k = 1;  int n = sizeof(arr) / sizeof(arr[0]);  cout << countSubarray(arr n k);  return 0; } // This code is contributed by Vaibhav Saroj
C 
#include  int countSubarray(int arr[] int n int k) {  int maxElement = 0 count = 0 ans = 0;  for(int i=0; i<n; i++) {  if(arr[i] > maxElement) {  maxElement = arr[i];  count = 0;  }  else {  count++;  }  if(maxElement > k) {  ans += (i - count + 1);  maxElement = arr[i];  count = 0;  }  }  ans += (count * (count + 1)) / 2;  return ans; } int main() {  int arr[] = {1 2 3 4};  int k = 1;  int n = sizeof(arr) / sizeof(arr[0]);  printf('%dn' countSubarray(arr n k));  return 0; } // This code is contributed by Vaibhav Saroj
Java 
import java.util.*; public class GFG {  // Function to count the number of subarrays with the maximum element greater than k  public static int countSubarray(int[] arr int n int k) {  int maxElement = 0; // Variable to store the maximum element encountered so far  int count = 0; // Variable to count the length of the subarray with elements <= k  int ans = 0; // Variable to store the final result  for (int i = 0; i < n; i++) {  if (arr[i] > maxElement) {  // If the current element is greater than the maximum element  // update the maximum element and reset the count to zero.  maxElement = arr[i];  count = 0;  } else {  // increment the count  count++;  }  if (maxElement > k) {  // If the maximum element in the current subarray is greater than k  // add the count of subarrays ending at the current index (i - count + 1) to the result.  ans += (i - count + 1);  // Reset the maximum element and count to zero.  maxElement = arr[i];  count = 0;  }  }  // Return the final result  return ans;  }  public static void main(String[] args) {  int[] arr = {1 2 3 4};  int k = 1;  int n = arr.length;  // Call the countSubarray function to count the number of subarrays with maximum element greater than k  int result = countSubarray(arr n k);  System.out.println(result);  } } // THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL
Python3 
def countSubarray(arr n k): maxElement count ans = 0 0 0 for i in range(n): if arr[i] > maxElement: maxElement = arr[i] count = 0 else: count += 1 if maxElement > k: ans += (i - count + 1) maxElement = arr[i] count = 0 ans += (count * (count + 1)) // 2 return ans arr = [1 2 3 4] k = 1 n = len(arr) print(countSubarray(arr n k)) # This code is contributed by Vaibhav Saroj
C# 
using System; public class Program {  public static int CountSubarray(int[] arr int n int k) {  int maxElement = 0 count = 0 ans = 0;  for(int i=0; i<n; i++) {  if(arr[i] > maxElement) {  maxElement = arr[i];  count = 0;  }  else {  count++;  }  if(maxElement > k) {  ans += (i - count + 1);  maxElement = arr[i];  count = 0;  }  }  ans += (count * (count + 1)) / 2;  return ans;  }  public static void Main() {  int[] arr = {1 2 3 4};  int k = 1;  int n = arr.Length;  Console.WriteLine(CountSubarray(arr n k));  } } // This code is contributed by Vaibhav Saroj
JavaScript 
function countSubarray(arr n k) {  let maxElement = 0 count = 0 ans = 0;  for(let i=0; i<n; i++) {  if(arr[i] > maxElement) {  maxElement = arr[i];  count = 0;  }  else {  count++;  }  if(maxElement > k) {  ans += (i - count + 1);  maxElement = arr[i];  count = 0;  }  }  ans += (count * (count + 1)) / 2;  return ans; } let arr = [1 2 3 4]; let k = 1; let n = arr.length; console.log(countSubarray(arr n k)); // This code is contributed by Vaibhav Saroj

Изход 
9

Техниката на плъзгащия се прозорец е предоставена от Вайбхав Сародж .

Времева сложност: O( n ).
Пространствена сложност: O( 1 ).

Практикувайте тук Брой подмасиви .

Създаване на тест