Dada una array arr[] de longitud N con elementos únicos, la tarea es encontrar la longitud de la subsecuencia creciente más larga que pueden formar los elementos de cualquier extremo de la array.
Ejemplos:
Entrada: arr[] = {3, 5, 1, 4, 2}
Salida: 4
Explicación:
La secuencia más larga es: {2, 3, 4, 5}
Elija 2, la secuencia es {2}, la array es {3, 5, 1, 4}
Elija 3, la secuencia es {2, 3}, la array es {5, 1, 4}
Elija 4, la secuencia es {2, 3, 4}, la array es {5, 1}
Elija 5, secuencia es {2, 3, 4, 5}, la array es {1}
Entrada: arr[] = {3, 1, 5, 2, 4}
Salida: 2
La secuencia más larga es {3, 4}
Enfoque: este problema se puede resolver mediante el enfoque de dos punteros . Establezca dos punteros en el primer y último índice de la array. Seleccione el mínimo de los dos valores señalados actualmente y verifique si es mayor que el valor seleccionado anteriormente. Si es así, actualice el puntero y aumente la longitud del LIS y repita el proceso. De lo contrario, imprima la longitud del LIS obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to print the
// longest increasing
// subsequence from the
// boundary elements of an array
#include <bits/stdc++.h>
using namespace std;
// Function to return the length of
// Longest Increasing subsequence
int longestSequence(int n, int arr[])
{
// Set pointers at
// both ends
int l = 0, r = n - 1;
// Stores the recent
// value added to the
// subsequence
int prev = INT_MIN;
// Stores the length of
// the subsequence
int ans = 0;
while (l <= r) {
// Check if both elements
// can be added to the
// subsequence
if (arr[l] > prev
&& arr[r] > prev) {
if (arr[l] < arr[r]) {
ans += 1;
prev = arr[l];
l += 1;
}
else {
ans += 1;
prev = arr[r];
r -= 1;
}
}
// Check if the element
// on the left can be
// added to the
// subsequence only
else if (arr[l] > prev) {
ans += 1;
prev = arr[l];
l += 1;
}
// Check if the element
// on the right can be
// added to the
// subsequence only
else if (arr[r] > prev) {
ans += 1;
prev = arr[r];
r -= 1;
}
// If none of the values
// can be added to the
// subsequence
else {
break;
}
}
return ans;
}
// Driver Code
int main()
{
int arr[] = { 3, 5, 1, 4, 2 };
// Length of array
int n = sizeof(arr)
/ sizeof(arr[0]);
cout << longestSequence(n, arr);
return 0;
}
Java
// Java program to print the longest
// increasing subsequence from the
// boundary elements of an array
import java.util.*;
class GFG{
// Function to return the length of
// Longest Increasing subsequence
static int longestSequence(int n, int arr[])
{
// Set pointers at
// both ends
int l = 0, r = n - 1;
// Stores the recent
// value added to the
// subsequence
int prev = Integer.MIN_VALUE;
// Stores the length of
// the subsequence
int ans = 0;
while (l <= r)
{
// Check if both elements
// can be added to the
// subsequence
if (arr[l] > prev &&
arr[r] > prev)
{
if (arr[l] < arr[r])
{
ans += 1;
prev = arr[l];
l += 1;
}
else
{
ans += 1;
prev = arr[r];
r -= 1;
}
}
// Check if the element on the
// left can be added to the
// subsequence only
else if (arr[l] > prev)
{
ans += 1;
prev = arr[l];
l += 1;
}
// Check if the element on the
// right can be added to the
// subsequence only
else if (arr[r] > prev)
{
ans += 1;
prev = arr[r];
r -= 1;
}
// If none of the values
// can be added to the
// subsequence
else
{
break;
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 5, 1, 4, 2 };
// Length of array
int n = arr.length;
System.out.print(longestSequence(n, arr));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to print the # longest increasing subsequence # from the boundary elements # of an array import sys # Function to return the length of # Longest Increasing subsequence def longestSequence(n, arr): # Set pointers at # both ends l = 0 r = n - 1 # Stores the recent value # added to the subsequence prev = -sys.maxsize - 1 # Stores the length of # the subsequence ans = 0 while (l <= r): # Check if both elements can be # added to the subsequence if (arr[l] > prev and arr[r] > prev): if (arr[l] < arr[r]): ans += 1 prev = arr[l] l += 1 else: ans += 1 prev = arr[r] r -= 1 # Check if the element # on the left can be # added to the # subsequence only elif (arr[l] > prev): ans += 1 prev = arr[l] l += 1 # Check if the element # on the right can be # added to the # subsequence only elif (arr[r] > prev): ans += 1 prev = arr[r] r -= 1 # If none of the values # can be added to the # subsequence else: break return ans # Driver code arr = [ 3, 5, 1, 4, 2 ] # Length of array n = len(arr) print(longestSequence(n, arr)) # This code is contributed by sanjoy_62
C#
// C# program to print the longest
// increasing subsequence from the
// boundary elements of an array
using System;
class GFG{
// Function to return the length of
// longest Increasing subsequence
static int longestSequence(int n, int []arr)
{
// Set pointers at
// both ends
int l = 0, r = n - 1;
// Stores the recent value
// added to the subsequence
int prev = int.MinValue;
// Stores the length of
// the subsequence
int ans = 0;
while (l <= r)
{
// Check if both elements
// can be added to the
// subsequence
if (arr[l] > prev &&
arr[r] > prev)
{
if (arr[l] < arr[r])
{
ans += 1;
prev = arr[l];
l += 1;
}
else
{
ans += 1;
prev = arr[r];
r -= 1;
}
}
// Check if the element on the
// left can be added to the
// subsequence only
else if (arr[l] > prev)
{
ans += 1;
prev = arr[l];
l += 1;
}
// Check if the element on the
// right can be added to the
// subsequence only
else if (arr[r] > prev)
{
ans += 1;
prev = arr[r];
r -= 1;
}
// If none of the values
// can be added to the
// subsequence
else
{
break;
}
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 3, 5, 1, 4, 2 };
// Length of array
int n = arr.Length;
Console.Write(longestSequence(n, arr));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript Program to print the
// longest increasing
// subsequence from the
// boundary elements of an array
// Function to return the length of
// Longest Increasing subsequence
function longestSequence(n, arr)
{
// Set pointers at
// both ends
var l = 0, r = n - 1;
// Stores the recent
// value added to the
// subsequence
var prev = -1000000000;
// Stores the length of
// the subsequence
var ans = 0;
while (l <= r) {
// Check if both elements
// can be added to the
// subsequence
if (arr[l] > prev
&& arr[r] > prev) {
if (arr[l] < arr[r]) {
ans += 1;
prev = arr[l];
l += 1;
}
else {
ans += 1;
prev = arr[r];
r -= 1;
}
}
// Check if the element
// on the left can be
// added to the
// subsequence only
else if (arr[l] > prev) {
ans += 1;
prev = arr[l];
l += 1;
}
// Check if the element
// on the right can be
// added to the
// subsequence only
else if (arr[r] > prev) {
ans += 1;
prev = arr[r];
r -= 1;
}
// If none of the values
// can be added to the
// subsequence
else {
break;
}
}
return ans;
}
// Driver Code
var arr = [ 3, 5, 1, 4, 2 ];
// Length of array
var n = arr.length;
document.write( longestSequence(n, arr));
// This code is contributed by itsok.
</script>
Producción:
4
Complejidad de tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por lostsoul27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA