Subarreglos más largos que tienen cada elemento del Array como el máximo

Dado un arreglo arr[] de longitud N , la tarea es encontrar el subarreglo más largo para cada elemento del arreglo arr[i] , que contiene arr[i] como máximo.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 0, 1} 
Salida: 1 2 5 1 2 
Explicación: 
El subarreglo más largo que tiene arr[0] como el más grande es {1} 
El subarreglo más largo que tiene arr[1] como el más grande es {1, 2} 
El subarreglo más largo que tiene arr[2] como el más grande es {1, 2, 3, 0, 1} 
El subarreglo más largo que tiene arr[3] como el más grande es {0} 
El subarreglo más largo que tiene arr[4 ya que el mayor es {0, 1}

Entrada: arr[] = {3, 3, 3, 1, 6, 2} 
Salida: 4 4 4 1 6 1

Enfoque: La idea es utilizar la técnica Two Pointer para resolver el problema: 

• Inicialice dos punteros, izquierdo y derecho . tal que para cada elemento arr[i] , la izquierda apunta a los índices [i – 1, 0] para encontrar elementos menores o iguales a arr[i] de manera contigua. En el momento en que se encuentra un elemento mayor que arr[i] , el puntero se detiene.
• De manera similar, la derecha apunta a los índices [i + 1, n – 1] para encontrar elementos menores o iguales a arr[i] de manera contigua, y se detiene al encontrar cualquier elemento mayor que arr[i].
• Por lo tanto, el subarreglo contiguo más grande donde arr[i] es más grande tiene una longitud de 1 + derecha – izquierda .
• Repita los pasos anteriores para cada elemento de la array.

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum length of
// Subarrays for each element of the array
// having it as the maximum
void solve(int n, int arr[])
{
    int i, ans = 0;
    for (i = 0; i < n; i++) {
 
        // Initialize the bounds
        int left = max(i - 1, 0);
        int right = min(n - 1, i + 1);
 
        // Iterate to find greater
        // element on the left
        while (left >= 0) {
 
            // If greater element is found
            if (arr[left] > arr[i]) {
                left++;
                break;
            }
 
            // Decrement left pointer
            left--;
        }
 
        // If boundary is exceeded
        if (left < 0)
            left++;
 
        // Iterate to find greater
        // element on the right
        while (right < n) {
 
            // If greater element is found
            if (arr[right] > arr[i]) {
                right--;
                break;
            }
            // Increment right pointer
            right++;
        }
 
        // If boundary is exceeded
        if (right >= n)
            right--;
 
        // Length of longest subarray where
        // arr[i] is the largest
        ans = 1 + right - left;
 
        // Print the answer
        cout << ans << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 4, 2, 1 };
    int n = sizeof arr / sizeof arr[0];
 
    solve(n, arr);
 
    return 0;
}

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
 
// Function to find the maximum length of
// Subarrays for each element of the array
// having it as the maximum
static void solve(int n, int arr[])
{
    int i, ans = 0;
    for (i = 0; i < n; i++)
    {
 
        // Initialize the bounds
        int left = Math.max(i - 1, 0);
        int right = Math.min(n - 1, i + 1);
 
        // Iterate to find greater
        // element on the left
        while (left >= 0)
        {
 
            // If greater element is found
            if (arr[left] > arr[i])
            {
                left++;
                break;
            }
 
            // Decrement left pointer
            left--;
        }
 
        // If boundary is exceeded
        if (left < 0)
            left++;
 
        // Iterate to find greater
        // element on the right
        while (right < n)
        {
 
            // If greater element is found
            if (arr[right] > arr[i])
            {
                right--;
                break;
            }
           
            // Increment right pointer
            right++;
        }
 
        // If boundary is exceeded
        if (right >= n)
            right--;
 
        // Length of longest subarray where
        // arr[i] is the largest
        ans = 1 + right - left;
 
        // Print the answer
        System.out.print(ans + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 4, 2, 1 };
    int n = arr.length;
 
    solve(n, arr);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program to implement
# the above approach
 
# Function to find the maximum length of
# Subarrays for each element of the array
# having it as the maximum
def solve(n, arr):
     
    ans = 0
     
    for i in range(n):
         
        # Initialise the bounds
        left = max(i - 1, 0)
        right = min(n - 1, i + 1)
         
        # Iterate to find greater
        # element on the left
        while left >= 0:
             
            # If greater element is found
            if arr[left] > arr[i]:
                left += 1
                break
                 
            # Decrement left pointer
            left -= 1
             
        # If boundary is exceeded
        if left < 0:
            left += 1
             
        # Iterate to find greater
        # element on the right
        while right < n:
             
            # If greater element is found
            if arr[right] > arr[i]:
                right -= 1
                break
             
            # Increment right pointer
            right += 1
         
        # if boundary is exceeded
        if right >= n:
            right -= 1
             
        # Length of longest subarray where
        # arr[i] is the largest
        ans = 1 + right - left
         
        # Print the answer
        print(ans, end = " ")
         
# Driver code
arr = [ 4, 2, 1 ]
n = len(arr)
 
solve(n, arr)
     
# This code is contributed by Stuti Pathak

// C# Program to implement
// the above approach
using System;
class GFG{
 
// Function to find the maximum length of
// Subarrays for each element of the array
// having it as the maximum
static void solve(int n, int []arr)
{
    int i, ans = 0;
    for (i = 0; i < n; i++)
    {
 
        // Initialize the bounds
        int left = Math.Max(i - 1, 0);
        int right = Math.Min(n - 1, i + 1);
 
        // Iterate to find greater
        // element on the left
        while (left >= 0)
        {
 
            // If greater element is found
            if (arr[left] > arr[i])
            {
                left++;
                break;
            }
 
            // Decrement left pointer
            left--;
        }
 
        // If boundary is exceeded
        if (left < 0)
            left++;
 
        // Iterate to find greater
        // element on the right
        while (right < n)
        {
 
            // If greater element is found
            if (arr[right] > arr[i])
            {
                right--;
                break;
            }
           
            // Increment right pointer
            right++;
        }
 
        // If boundary is exceeded
        if (right >= n)
            right--;
 
        // Length of longest subarray where
        // arr[i] is the largest
        ans = 1 + right - left;
 
        // Print the answer
        Console.Write(ans + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 4, 2, 1 };
    int n = arr.Length;
 
    solve(n, arr);
}
}
 
// This code is contributed by Princi Singh

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to find the maximum length of
// Subarrays for each element of the array
// having it as the maximum
function solve(n, arr)
{
    let i, ans = 0;
    for (i = 0; i < n; i++)
    {
   
        // Initialize the bounds
        let left = Math.max(i - 1, 0);
        let right = Math.min(n - 1, i + 1);
   
        // Iterate to find greater
        // element on the left
        while (left >= 0)
        {
   
            // If greater element is found
            if (arr[left] > arr[i])
            {
                left++;
                break;
            }
   
            // Decrement left pointer
            left--;
        }
   
        // If boundary is exceeded
        if (left < 0)
            left++;
   
        // Iterate to find greater
        // element on the right
        while (right < n)
        {
   
            // If greater element is found
            if (arr[right] > arr[i])
            {
                right--;
                break;
            }
             
            // Increment right pointer
            right++;
        }
   
        // If boundary is exceeded
        if (right >= n)
            right--;
   
        // Length of longest subarray where
        // arr[i] is the largest
        ans = 1 + right - left;
   
        // Print the answer
        document.write(ans + " ");
    }
}
 
// Driver Code
 
    let arr = [ 4, 2, 1 ];
    let n = arr.length;
   
    solve(n, arr);
                 
</script>

3 2 1

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