Дано масив п елементів і ціле число k . Завдання полягає в тому, щоб знайти кількість підмасиву, максимальний елемент якого перевищує K.
Приклади:
Input : arr[] = {1 2 3} and k = 2.Recommended Practice Кількість підмасивів Спробуйте!
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.
Підхід 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
// 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.
<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 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 .
- Кількість підмасивів, починаючи з індексу i . Це буде ( N - i ) . ПРИМІТКА. Сюди ми включили підмасив, що містить один елемент, який є самим цим елементом. { arr [ i ] }
- Кількість підмасивів, що закінчуються цим індексом i але початковий індекс цих підмасивів знаходиться після індексу поперед попереднього елемента, який був більшим за K, чому ми це робимо? Тому що для цих елементів ми повинні вже обчислити нашу відповідь, тому ми не хочемо рахувати ті самі підмасиви більше одного разу. Отже, це значення буде мати місце ( i - попередня - 1 ) . ПРИМІТКА. У цьому випадку ми віднімаємо 1, тому що ми вже підрахували підмасив { arr [ i ] }, який є одним елементом. Див. примітку вище.
- Кількість підмасивів із початковим індексом менше ніж i але більше ніж поперед і кінцевий індекс більше ніж i . Тому всі підмасиви, в яких arr[i] знаходиться між ними. Це можна обчислити, помноживши вище два значення. Скажімо, як L = ( N - i - 1 ) і R = ( i - попередня -1 ). Тепер ми просто перемножуємо ці L і R, тому що для кожного 1 індексу ліворуч від i є індекс R, який може створювати різні підмасиви для базової математики. Так це стає L * R . Зверніть увагу, що тут у значенні L ми фактично відняли 1, якщо ми цього не робимо, тоді ми включаємо індекс i у наш L*R, що означатиме, що ми знову включили підмасиви типу номер 1. Дивіться пункт 1.
Нижче наведено реалізацію цього підходу:
C++// C++ program to count number of subarrays // whose maximum element is greater than K. #include
// 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
# 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# 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 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. Перебирайте масив, виконуючи такі дії для кожного елемента:
a. Якщо поточний елемент, тобто arr[ i ] більше поточного максимуму оновити максимум, тобто Радіо = arr ] і скиньте рахунок до 0.
b. Якщо поточний елемент менший або дорівнює поточному максимуму, збільште кількість.
в. Якщо maxElement grteater ніж k тоді додати кількість підмасивів до остаточної відповіді та оновлення maxElement до поточного елемента.
3. Повернути Остаточна відповідь.
Ось реалізація техніки розсувного вікна.
C++#include
#include
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
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
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
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 ).