Recuento de todos los subarreglos bitónicos posibles

Dada una array arr[] que consta de N enteros, la tarea es contar todos los subarreglos que son de naturaleza bitónica . 
 

Un subarreglo bitónico es un subarreglo en el que los elementos son estrictamente crecientes o estrictamente decrecientes, o primero son crecientes y luego decrecientes.

Ejemplos: 
 

Entrada: arr[] = {2, 1, 4, 5} 
Salida: 8 
Explicación: 
Todos los subarreglos que son bitónicos en el subarreglo son: {2}, {2, 1}, {1}, {1, 4}, { 1, 4, 5}, {4}, {4, 5} y {5}.
Entrada: arr[] = {1, 2, 3, 4} 
Salida: 10 
 

Enfoque: 
siga los pasos a continuación para resolver los problemas: 
 

1. Genere todos los subarreglos posibles.
2. Para cada subarreglo, verifique si es bitónico o no. Si el subarreglo es bitónico , incremente el conteo para la respuesta.
3. Finalmente devuelva la respuesta.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to count the
// number of possible
// bitonic subarrays
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count
// of bitonic subarrays
void countbitonic(int arr[], int n)
{
    int c = 0;
    // Starting element of subarray
    for (int i = 0; i < n; i++) {
        // Ending element of subarray
        for (int j = i; j < n; j++) {
 
            int temp = arr[i], f = 0;
 
            // for 1 length
            if (j == i) {
                c++;
                continue;
            }
 
            int k = i + 1;
 
            // For increasing sequence
            while (temp < arr[k] && k <= j) {
                temp = arr[k];
                k++;
            }
 
            // If strictly increasing
            if (k > j) {
                c++;
                f = 2;
            }
 
            // For decreasing sequence
            while (temp > arr[k]
                   && k <= j
                   && f != 2) {
                temp = arr[k];
                k++;
            }
 
            if (k > j && f != 2) {
                c++;
                f = 0;
            }
        }
    }
 
    cout << c << endl;
}
// Driver Code
int main()
{
    int arr[] = { 1, 2, 4, 3, 6, 5 };
    int N = 6;
 
    countbitonic(arr, N);
}

// Java program to count the number
// of possible bitonic subarrays
import java.io.*;
import java.util.*;
 
class GFG{
     
// Function to return the count
// of bitonic subarrays
public static void countbitonic(int arr[], int n)
{
    int c = 0;
     
    // Starting element of subarray
    for(int i = 0; i < n; i++)
    {
         
       // Ending element of subarray
       for(int j = i; j < n; j++)
       {
          int temp = arr[i], f = 0;
           
          // For 1 length
          if (j == i)
          {
              c++;
              continue;
          }
          int k = i + 1;
           
          // For increasing sequence
          while (temp < arr[k] && k <= j)
          {
              temp = arr[k];
              k++;
          }
           
          // If strictly increasing
          if (k > j)
          {
              c++;
              f = 2;
          }
           
          // For decreasing sequence
          while ( k <= j && temp > arr[k] && f != 2)
          {
              temp = arr[k];
              k++;
          }
          if (k > j && f != 2)
          {
              c++;
              f = 0;
          }
       }
    }
    System.out.println(c);
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 4, 3, 6, 5 };
    int N = 6;
     
    countbitonic(arr, N);
}
}
 
// This code is contributed by grand_master

# Python3 program to count the number
# of possible bitonic subarrays
 
# Function to return the count
# of bitonic subarrays
def countbitonic(arr, n):
 
    c = 0;
     
    # Starting element of subarray
    for i in range(n):
         
        # Ending element of subarray
        for j in range(i, n):
            temp = arr[i]
            f = 0;
 
            # For 1 length
            if (j == i) :
                c += 1
                continue;
            k = i + 1;
 
            # For increasing sequence
            while (temp < arr[k] and k <= j):
                temp = arr[k];
                k += 1
                 
            # If strictly increasing
            if (k > j) :
                c += 1
                f = 2;
                 
            # For decreasing sequence
            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(c)
     
# Driver Code
arr = [ 1, 2, 4, 3, 6, 5 ];
N = 6;
 
countbitonic(arr, N);
 
# This code is contributed by grand_master

// C# program to count the number
// of possible bitonic subarrays
using System;
 
class GFG{
 
// Function to return the count
// of bitonic subarrays    
public static void countbitonic(int []arr, int n)
{
    int c = 0;
     
    // Starting element of subarray
    for(int i = 0; i < n; i++)
    {
         
       // Ending element of subarray
       for(int j = i; j < n; j++)
       {
          int temp = arr[i], f = 0;
           
          // for 1 length
          if (j == i)
          {
              c++;
              continue;
          }
          int k = i + 1;
           
          // For increasing sequence
          while (temp < arr[k] && k <= j)
          {
              temp = arr[k];
              k++;
          }
           
          // If strictly increasing
          if (k > j)
          {
              c++;
              f = 2;
          }
           
          // For decreasing sequence
          while ( k <= j && temp > arr[k] && f != 2)
          {
              temp = arr[k];
              k++;
          }
          if (k > j && f != 2)
          {
              c++;
              f = 0;
          }
       }
    }
    Console.Write(c);
}
 
// Driver code
public static void Main()
{
    int[] arr = { 1, 2, 4, 3, 6, 5 };
    int N = 6;
     
    countbitonic(arr, N);
}
}
 
// This code is contributed by grand_master

<script>
 
// Javascript program to count the
// number of possible
// bitonic subarrays
 
// Function to return the count
// of bitonic subarrays
function countbitonic(arr, n)
{
    var c = 0;
     
    // Starting element of subarray
    for (var i = 0; i < n; i++)
    {
     
        // Ending element of subarray
        for (var j = i; j < n; j++)
        {
 
            var temp = arr[i], f = 0;
 
            // for 1 length
            if (j == i)
            {
                c++;
                continue;
            }
 
            var k = i + 1;
 
            // For increasing sequence
            while (temp < arr[k] && k <= j) {
                temp = arr[k];
                k++;
            }
 
            // If strictly increasing
            if (k > j) {
                c++;
                f = 2;
            }
 
            // For decreasing sequence
            while (temp > arr[k]
                   && k <= j
                   && f != 2) {
                temp = arr[k];
                k++;
            }
 
            if (k > j && f != 2) {
                c++;
                f = 0;
            }
        }
    }
 
    document.write( c );
}
 
// Driver Code
var arr = [1, 2, 4, 3, 6, 5];
var N = 6;
countbitonic(arr, N);
 
// This code is contributed by rutvik_56.
</script>

15

Complejidad Temporal: O (N ³ )  
Espacio Auxiliar: O (1)