Recuento de todos los subarreglos bitónicos inversos posibles

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:
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:
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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *