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++
// 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
// 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
# 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#
// 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
Javascript
<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>
Producción:
3 2 1
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Ripunjoy Medhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA