Secuencia creciente más larga por los elementos de contorno de una array

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:
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:
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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *