Longitud del subarreglo más largo con elementos más pequeños inmediatamente a la izquierda para cada elemento del Array

Dado un arreglo arr[] de longitud N , la tarea es encontrar la longitud del subarreglo más largo con elementos más pequeños a la izquierda inmediata para cada elemento en el arreglo dado.

Ejemplo:

Entrada: arr[] = { 2, 1, 7, 6, 7 }
Salida: 0 0 2 0 1
Explicación: 
Índice 0 (2): No hay ninguna substring presente a la izquierda inmediata que tenga todos los elementos más pequeños. Por lo tanto, longitud = 0
Índice 1 (1): ninguna substring está presente inmediatamente a la izquierda y tiene todos los elementos más pequeños. Entonces, longitud=0
Índice 2 (7): La substring {2, 1} está presente inmediatamente a la izquierda y tiene todos los elementos más pequeños. Por lo tanto, longitud = 2
Índice 3 (6): ninguna substring está presente a la izquierda inmediata que tiene todos los elementos más pequeños. Entonces, longitud=0
Índice 4 (2): La substring {6} está presente inmediatamente a la izquierda y tiene todos los elementos más pequeños. Entonces, longitud = 1

Entrada: arr[] = { 4, 5, 7, 6, 10 }
Salida: 0 1 2 0 4

Enfoque: para cada elemento, viaje hacia su izquierda hasta que el elemento de la izquierda sea mayor o el arreglo termine para encontrar la longitud del subarreglo más largo con elementos más pequeños a la izquierda inmediata. Siga los pasos a continuación para resolver este problema:

1. Recorra cada elemento en la array arr[] .
2. Para cada elemento, ejecute otro bucle en la dirección izquierda.
   • Cuente todos los elementos más pequeños que el elemento actual hasta que llegue un elemento mayor o termine la array.
3. Escriba la respuesta de acuerdo con la observación anterior.

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

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function to find the length of the longest
// subarray with smaller elements on the immediate
// left for each element in the given array
void subarrayLength(int* arr, int n)
{
    for (int i = 0; i < n; i++) {
        int ans = 0;
        for (int j = i - 1; j >= 0; j--) {
 
            // If a greater element comes
            if (arr[i] <= arr[j]) {
                break;
            }
            // Else
            ans++;
        }
        cout << ans << " ";
    }
}
 
// Driver Code
int main()
{
 
    int n = 5;
    int arr[n] = { 1, 4, 2, 6, 3 };
    subarrayLength(arr, n);
    return 0;
}

// Java program for the above approach
class GFG{
 
// Function to find the length of the longest
// subarray with smaller elements on the immediate
// left for each element in the given array
static void subarrayLength(int arr[], int n)
{
    for(int i = 0; i < n; i++)
    {
        int ans = 0;
        for(int j = i - 1; j >= 0; j--)
        {
             
            // If a greater element comes
            if (arr[i] <= arr[j])
            {
                break;
            }
             
            // Else
            ans++;
        }
        System.out.print(ans + " ");
    }
}
 
// Driver Code
public static void main(String args[])
{
    int n = 5;
    int arr[] = { 1, 4, 2, 6, 3 };
     
    subarrayLength(arr, n);
}
}
 
// This code is contributed by gfgking

# Python program for the above approach
 
# Function to find the length of the longest
# subarray with smaller elements on the immediate
# left for each element in the given array
def subarrayLength(arr, n):
 
    for i in range(0, n):
        ans = 0
        for j in range(i-1, -1, -1):
 
            # If a greater element comes
            if (arr[i] <= arr[j]):
                break
 
            # Else
            ans += 1
        print(ans, end=" ")
 
# Driver Code
if __name__ == "__main__":
 
    n = 5
    arr = [1, 4, 2, 6, 3]
    subarrayLength(arr, n)
 
# This code is contributed by rakeshsahni

// C# program for the above approach
using System;
class GFG{
 
// Function to find the length of the longest
// subarray with smaller elements on the immediate
// left for each element in the given array
static void subarrayLength(int []arr, int n)
{
    for(int i = 0; i < n; i++)
    {
        int ans = 0;
        for(int j = i - 1; j >= 0; j--)
        {
             
            // If a greater element comes
            if (arr[i] <= arr[j])
            {
                break;
            }
             
            // Else
            ans++;
        }
        Console.Write(ans + " ");
    }
}
 
// Driver Code
public static void Main()
{
    int n = 5;
    int []arr = { 1, 4, 2, 6, 3 };
     
    subarrayLength(arr, n);
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
      // JavaScript code for the above approach
 
      // Function to find the length of the longest
      // subarray with smaller elements on the immediate
      // left for each element in the given array
      function subarrayLength(arr, n)
      {
          for (let i = 0; i < n; i++)
          {
              let ans = 0;
              for (let j = i - 1; j >= 0; j--) {
 
                  // If a greater element comes
                  if (arr[i] <= arr[j]) {
                      break;
                  }
                   
                  // Else
                  ans++;
              }
              document.write(ans + " ");
          }
      }
 
      // Driver Code
      let n = 5;
      let arr = [1, 4, 2, 6, 3];
      subarrayLength(arr, n);
 
// This code is contributed by Potta Lokesh
  </script>

0 1 0 3 0 

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)