Dada una array arr[] de N enteros, la tarea es contar el número total de subarreglo bitónico inverso de la array dada.
Un subarreglo bitónico inverso es un subarreglo en el que los elementos se organizan en orden decreciente y luego se ordenan en orden creciente. Un subarreglo estrictamente creciente o estrictamente decreciente también se considera un subarreglo bitónico inverso.
Ejemplos:
Entrada: arr[] = {2, 3, 1, 4}
Salida: 8
Explicación:
Aquí buscaremos todos los subarreglos de longitud de una array dada
. Para la longitud 1, todos los subarreglos son subarreglos bitónicos inversos {2}, {3}, {1}, {4}
Para la longitud 2, los subarreglos posibles son {2, 3}, {3, 1}, {1, 4}
Para la longitud 3, el subarreglo posible es {3, 1, 4}
Entonces, en total, hay Hay 8 subarreglos posibles.
Entrada: arr[] = [1, 2, 3]
Salida: 6
Explicación:
Aquí buscaremos todos los subarreglos de longitud de una array dada
Para la longitud 1, todos los subarreglos son bitónicos inversos {1}, {2}, {3}
Para la longitud 2, los subarreglos posibles son {1, 2}, {2, 3}
Para la longitud 3, los subarreglos posibles son {1, 2, 3}.
Entonces, en total, hay 6 subarreglos posibles.
Enfoque: La idea es generar todos los subarreglos a partir del arreglo dado y verificar si cada subarreglo cumple con las condiciones mencionadas a continuación:
- Cuando los elementos del subarreglo aumentan estrictamente, tome el primer elemento y luego verifique que el siguiente aumente.
- Cuando los elementos del subarreglo son estrictamente decrecientes, tome el primer elemento y luego verifique que el siguiente sea decreciente.
- Cuando los elementos del subarreglo son estrictamente decrecientes y luego aumentan, entonces, en ese caso, tome el primer elemento y luego verifique si está al lado de la disminución y cuando se vuelve falso, luego verifique si aumenta hasta el último elemento.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that counts all the reverse // bitonic subarray in arr[] void countReversebitonic(int arr[], int n) { // To store the count of reverse // bitonic subarray int c = 0; // Iterate the array and select // the starting element for (int i = 0; i < n; i++) { // Iterate for selecting the // ending element for subarray for (int j = i; j < n; j++) { // Subarray arr[i to j] int temp = arr[i], f = 0; // For 1 length, increment // the count and continue if (j == i) { c++; continue; } int k = i + 1; // For Decreasing Subarray while (temp > arr[k] && k <= j) { temp = arr[k]; k++; } // Check if only Decreasing if (k > j) { c++; f = 2; } // For Increasing Subarray while (temp < arr[k] && k <= j && f != 2) { temp = arr[k]; k++; } if (k > j && f != 2) { c++; f = 0; } } } // Print the total count of subarrays cout << c << endl; } // Driver Code int main() { // Given array arr[] int arr[] = { 2, 3, 1, 4 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call countReversebitonic(arr, N); }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function that counts all the reverse // bitonic subarray in arr[] static void countReversebitonic(int arr[], int n) { // To store the count of reverse // bitonic subarray int c = 0; // Iterate the array and select // the starting element for(int i = 0; i < n; i++) { // Iterate for selecting the // ending element for subarray for(int j = i; j < n; j++) { // Subarray arr[i to j] int temp = arr[i], f = 0; // For 1 length, increment // the count and continue if (j == i) { c++; continue; } int k = i + 1; // For decreasing subarray while (temp > arr[k] && k <= j) { temp = arr[k]; k++; } // Check if only decreasing if (k > j) { c++; f = 2; } // For increasing subarray while (k <= j && temp < arr[k] && f != 2) { temp = arr[k]; k++; } if (k > j && f != 2) { c++; f = 0; } } } // Print the total count of subarrays System.out.print(c + "\n"); } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 2, 3, 1, 4 }; int N = arr.length; // Function Call countReversebitonic(arr, N); } } // This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach # Function that counts all the reverse # bitonic subarray in arr[] def countReversebitonic(arr, n): # To store the count of reverse # bitonic subarray c = 0; # Iterate the array and select # the starting element for i in range(n): # Iterate for selecting the # ending element for subarray for j in range(i, n): # Subarray arr[i to j] temp = arr[i] f = 0; # For 1 length, increment # the count and continue if (j == i): c += 1; continue; k = i + 1; # For Decreasing Subarray while (k <= j and temp > arr[k]): temp = arr[k]; k += 1; # Check if only Decreasing if (k > j): c += 1; f = 2; # For Increasing Subarray while (k <= j and temp < arr[k] and f != 2): temp = arr[k]; k += 1; if (k > j and f != 2): c += 1; f = 0; # Print the total count of subarrays print(c) # Driver Code # Given array arr[] arr = [ 2, 3, 1, 4 ]; # Function Call countReversebitonic(arr, len(arr)); # This code is contributed by grand_master
C#
// C# program for the above approach using System; class GFG{ // Function that counts all the reverse // bitonic subarray in arr[] static void countReversebitonic(int []arr, int n) { // To store the count of reverse // bitonic subarray int c = 0; // Iterate the array and select // the starting element for(int i = 0; i < n; i++) { // Iterate for selecting the // ending element for subarray for(int j = i; j < n; j++) { // Subarray arr[i to j] int temp = arr[i], f = 0; // For 1 length, increment // the count and continue if (j == i) { c++; continue; } int k = i + 1; // For decreasing subarray while (temp > arr[k] && k <= j) { temp = arr[k]; k++; } // Check if only decreasing if (k > j) { c++; f = 2; } // For increasing subarray while (k <= j && temp < arr[k] && f != 2) { temp = arr[k]; k++; } if (k > j && f != 2) { c++; f = 0; } } } // Print the total count of subarrays Console.Write(c); } // Driver Code public static void Main(string[] args) { // Given array arr[] int []arr = { 2, 3, 1, 4 }; int N = arr.Length; // Function Call countReversebitonic(arr, N); } } // This code is contributed by Ritik Bansal
Javascript
<script> // JavaScript program for the above approach // Function that counts all the reverse // bitonic subarray in arr[] function countReversebitonic(arr, n) { // To store the count of reverse // bitonic subarray let c = 0; // Iterate the array and select // the starting element for(let i = 0; i < n; i++) { // Iterate for selecting the // ending element for subarray for(let j = i; j < n; j++) { // Subarray arr[i to j] let temp = arr[i], f = 0; // For 1 length, increment // the count and continue if (j == i) { c++; continue; } let k = i + 1; // For decreasing subarray while (temp > arr[k] && k <= j) { temp = arr[k]; k++; } // Check if only decreasing if (k > j) { c++; f = 2; } // For increasing subarray while (k <= j && temp < arr[k] && f != 2) { temp = arr[k]; k++; } if (k > j && f != 2) { c++; f = 0; } } } // Print the total count of subarrays document.write(c + "<br/>"); } // Driver Code // Given array arr[] let arr = [ 2, 3, 1, 4 ]; let N = arr.length; // Function Call countReversebitonic(arr, N); </script>
8
Complejidad de tiempo: O(N 2 ) , donde N es el número de elementos en la array dada.
Publicación traducida automáticamente
Artículo escrito por grand_master y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA