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