Dada una array arr[] que contiene una permutación aleatoria de los primeros N números naturales, la tarea es encontrar la subsecuencia más larga que tenga la propiedad de que el primero y el último elemento son mayores que todos los demás elementos de la subsecuencia.
Ejemplos:
Entrada: arr[] = {3, 1, 5, 2, 4}
Salida: 4
La subsecuencia es {3, 1, 2, 4}. Los elementos de esquina de esta subsecuencia son mayores que todos los demás elementos.
Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: 2
No podemos hacer una subsecuencia de tamaño mayor que 2.
Enfoque: si fijamos los elementos más a la izquierda y más a la derecha de una subsecuencia, nos interesa contar cuántos elementos entre ellos tienen un valor menor que ambos. Una implementación sencilla de esta idea tiene una complejidad de O(N 3 ).
Para reducir la complejidad, abordamos el problema de manera diferente. En lugar de fijar los extremos de la subsecuencia, fijamos los elementos intermedios. La idea es que para una X dada (1 ≤ X ≤ N), queremos encontrar dos elementos mayores o iguales a X, que tengan entre ellos tantos elementos como sea posible menores que X. Para una X fija es óptimo elegir el elementos más a la izquierda y más a la derecha ≤ X. Ahora tenemos una mejor solución O(N 2 ).
A medida que X aumenta, el elemento más a la izquierda solo puede aumentar, mientras que el más a la derecha solo puede disminuir. Podemos usar un puntero para cada uno de ellos para obtener una complejidad amortizada de O(N).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
// Function to return the length of the
// longest required sub-sequence
int longestSubSeq(int n, int arr [])
{
int max_length = 0;
// Create a position array to find
// where an element is present
int pos[MAXN];
for (int i = 0; i < n; i++)
pos[arr[i] - 1] = i;
int left = n, right = 0;
for (int i = n - 1, num = 1; i >= 0;
i -= 1, num += 1)
{
// Store the minimum position
// to the left
left = min(left, pos[i]);
// Store the maximum position to
// the right
right = max(right, pos[i]);
// Recompute current maximum
max_length = max(max_length,
right - left - num + 3);
}
// Edge case when there is a single
// element in the sequence
if (n == 1)
max_length = 1;
return max_length;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << longestSubSeq(n, arr);
}
// This code is contributed by ihritik
Java
// Java implementation of the approach
class GFG {
static int MAXN = (int)1e5 + 5;
// Function to return the length of the
// longest required sub-sequence
static int longestSubSeq(int n, int[] arr)
{
int max_length = 0;
// Create a position array to find
// where an element is present
int[] pos = new int[MAXN];
for (int i = 0; i < n; i++)
pos[arr[i] - 1] = i;
int left = n, right = 0;
for (int i = n - 1, num = 1; i >= 0;
i -= 1, num += 1) {
// Store the minimum position
// to the left
left = Math.min(left, pos[i]);
// Store the maximum position to
// the right
right = Math.max(right, pos[i]);
// Recompute current maximum
max_length = Math.max(max_length,
right - left - num + 3);
}
// Edge case when there is a single
// element in the sequence
if (n == 1)
max_length = 1;
return max_length;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = arr.length;
System.out.println(longestSubSeq(n, arr));
}
}
Python3
# Python3 implementation of the approach MAXN = 100005 # Function to return the length of the # longest required sub-sequence def longestSubSeq(n, arr): max_length = 0 # Create a position array to find # where an element is present pos = [0] * MAXN for i in range (0, n): pos[arr[i] - 1] = i left = n right = 0 num = 1 for i in range (n - 1, -1, -1) : # Store the minimum position # to the left left = min(left, pos[i]) # Store the maximum position to # the right right = max(right, pos[i]) # Recompute current maximum max_length = max(max_length, right - left - num + 3) num = num + 1 # Edge case when there is a single # element in the sequence if (n == 1) : max_length = 1 return max_length # Driver code arr = [ 1, 2, 3, 4, 5 ] n = len(arr) print(longestSubSeq(n, arr)) # This code is contributed by ihritik
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAXN = (int)1e5 + 5;
// Function to return the length of the
// longest required sub-sequence
static int longestSubSeq(int n, int[] arr)
{
int max_length = 0;
// Create a position array to find
// where an element is present
int[] pos = new int[MAXN];
for (int i = 0; i < n; i++)
pos[arr[i] - 1] = i;
int left = n, right = 0;
for (int i = n - 1, num = 1; i >= 0;
i -= 1, num += 1)
{
// Store the minimum position
// to the left
left = Math.Min(left, pos[i]);
// Store the maximum position to
// the right
right = Math.Max(right, pos[i]);
// Recompute current maximum
max_length = Math.Max(max_length,
right - left - num + 3);
}
// Edge case when there is a single
// element in the sequence
if (n == 1)
max_length = 1;
return max_length;
}
// Driver code
public static void Main()
{
int []arr = { 1, 2, 3, 4, 5 };
int n = arr.Length;
Console.WriteLine(longestSubSeq(n, arr));
}
}
// This code is contributed by Ryuga
PHP
<?php
// PHP implementation of the approach
$MAXN = 100005;
// Function to return the length of the
// longest required sub-sequence
function longestSubSeq($n, $arr)
{
global $MAXN;
$max_length = 0;
// Create a position array to find
// where an element is present
$pos = array();
for ($i = 0; $i < $n; $i++)
$pos[$arr[$i] - 1] = $i;
$left = $n;
$right = 0;
$num = 1;
for ($i = $n - 1; $i >= 0 ; $i--, $num++)
{
// Store the minimum position
// to the left
$left = min($left, $pos[$i]);
// Store the maximum position to
// the right
$right = max($right, $pos[$i]);
// Recompute current maximum
$max_length = max($max_length,
$right - $left - $num + 3);
}
// Edge case when there is a single
// element in the sequence
if ($n == 1)
$max_length = 1;
return $max_length;
}
// Driver code
$arr = array(1, 2, 3, 4, 5);
$n = sizeof($arr);
echo longestSubSeq($n, $arr);
// This code is contributed by ihritik
?>
Javascript
<script>
// JavaScript implementation of the approach
let MAXN = 1e5 + 5;
// Function to return the length of the
// longest required sub-sequence
function longestSubSeq(n, arr)
{
let max_length = 0;
// Create a position array to find
// where an element is present
let pos = new Array(MAXN);
pos.fill(0);
for (let i = 0; i < n; i++)
pos[arr[i] - 1] = i;
let left = n, right = 0;
for (let i = n - 1, num = 1; i >= 0;
i -= 1, num += 1)
{
// Store the minimum position
// to the left
left = Math.min(left, pos[i]);
// Store the maximum position to
// the right
right = Math.max(right, pos[i]);
// Recompute current maximum
max_length = Math.max(max_length,
right - left - num + 3);
}
// Edge case when there is a single
// element in the sequence
if (n == 1)
max_length = 1;
return max_length;
}
let arr = [ 1, 2, 3, 4, 5 ];
let n = arr.length;
document.write(longestSubSeq(n, arr));
</script>
2
Publicación traducida automáticamente
Artículo escrito por AmanKumarSingh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA