La subsecuencia más larga de una array de pares que tiene un primer elemento creciente y un segundo elemento decreciente.

Dada una array de pares A[][] de tamaño N , la tarea es encontrar las subsecuencias más largas donde el primer elemento es creciente y el segundo elemento es decreciente.

Ejemplos:

Entrada: A[]={{ 1, 2}, {2, 2}, {3, 1}}, N = 3
Salida: 2
Explicación: La subsecuencia más larga que satisface las condiciones es de longitud 2 y consta de {1, 2} y {3, 1};

Entrada: A[] = {{1, 3}, {2, 5}, {3, 2}, {5, 2}, {4, 1}}, N = 5
Salida: 3

Enfoque ingenuo: el enfoque más simple es usar Recursion . Para cada par en la array, hay dos opciones posibles, es decir, incluir el par actual en la subsecuencia o no. Por lo tanto, itere sobre la array recursivamente y encuentre la subsecuencia más larga requerida.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Recursive function to find the length of
// the longest subsequence of pairs whose first
// element is increasing and second is decreasing
int longestSubSequence(pair<int, int> A[], int N,
                       int ind = 0,
                       int lastf = INT_MIN,
                       int lasts = INT_MAX)
{
 
    // Base case
    if (ind == N)
        return 0;
 
    // Not include the current pair
    // in the longest subsequence
    int ans = longestSubSequence(A, N, ind + 1,
                                 lastf, lasts);
 
    // Including the current pair
    // in the longest subsequence
    if (A[ind].first > lastf
        && A[ind].second < lasts)
 
        ans = max(ans, longestSubSequence(A, N, ind + 1,
                                          A[ind].first,
                                          A[ind].second)
                           + 1);
 
    return ans;
}
 
// Driver Code
int main()
{
    // Given Input
    pair<int, int> A[] = { { 1, 2 },
                           { 2, 2 },
                           { 3, 1 } };
 
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function Call
    cout << longestSubSequence(A, N) << "\n";
 
    return 0;
}

Java

// Java program for the above approach
class GFG{
     
// Recursive function to find the length of
// the longest subsequence of pairs whose first
// element is increasing and second is decreasing
public static Integer longestSubSequence(int[][] A, int N, int ind,
                                         int lastf, int lasts)
{
    ind = (ind > 0 ? ind : 0);
    lastf = (lastf > 0 ? lastf: Integer.MIN_VALUE);
    lasts = (lasts > 0 ? lasts: Integer.MAX_VALUE);
     
    // Base case
    if (ind == N)
        return 0;
 
    // Not include the current pair
    // in the longest subsequence
    int ans = longestSubSequence(A, N, ind + 1,
                                 lastf, lasts);
 
    // Including the current pair
    // in the longest subsequence
    if (A[ind][0] > lastf && A[ind][1] < lasts)
 
        ans = Math.max(ans, longestSubSequence(A, N, ind + 1,
                                   A[ind][0], A[ind][1]) + 1);
 
    return ans;
}
 
public static int longestSubSequence(int[][] A, int N)
{
    return longestSubSequence(A, N, 0, 0, 0);
}
 
// Driver Code
public static void main(String args[])
{
     
    // Given Input
    int[][] A = { { 1, 2 }, { 2, 2 }, { 3, 1 } };
    int N = A.length;
 
    // Function Call
    System.out.println(longestSubSequence(A, N));
}
}
 
// This code is contributed by _saurabh_jaiswal

Python3

# Python 3 program for the above approach
import sys
 
# Recursive function to find the length of
# the longest subsequence of pairs whose first
# element is increasing and second is decreasing
def longestSubSequence(A,  N,
                       ind=0,
                       lastf=-sys.maxsize-1,
                       lasts=sys.maxsize):
 
    # Base case
    if (ind == N):
        return 0
 
    # Not include the current pair
    # in the longest subsequence
    ans = longestSubSequence(A, N, ind + 1,
                             lastf, lasts)
 
    # Including the current pair
    # in the longest subsequence
    if (A[ind][0] > lastf
            and A[ind][1] < lasts):
 
        ans = max(ans, longestSubSequence(A, N, ind + 1,
                                          A[ind][0],
                                          A[ind][1])
                  + 1)
 
    return ans
 
 
# Driver Code
if __name__ == "__main__":
 
    # Given Input
    A = [[1, 2],
         [2, 2],
         [3, 1]]
 
    N = len(A)
     
    # Function Call
    print(longestSubSequence(A, N))
 
    # This code is contributed by ukasp.

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Recursive function to find the length of
// the longest subsequence of pairs whose first
// element is increasing and second is decreasing
public static int longestSubSequence(int[,] A, int N, int ind,
                                         int lastf, int lasts)
{
    ind = (ind > 0 ? ind : 0);
    lastf = (lastf > 0 ? lastf: Int32.MinValue);
    lasts = (lasts > 0 ? lasts: Int32.MaxValue);
     
    // Base case
    if (ind == N)
        return 0;
 
    // Not include the current pair
    // in the longest subsequence
    int ans = longestSubSequence(A, N, ind + 1,
                                 lastf, lasts);
 
    // Including the current pair
    // in the longest subsequence
    if (A[ind, 0] > lastf && A[ind, 1] < lasts)
 
        ans = Math.Max(ans, longestSubSequence(A, N, ind + 1,
                                   A[ind, 0], A[ind, 1]) + 1);
 
    return ans;
}
 
public static int longestSubSequence(int[,] A, int N)
{
    return longestSubSequence(A, N, 0, 0, 0);
}
 
// Driver Code
public static void Main()
{
    // Given Input
    int[,] A = { { 1, 2 }, { 2, 2 }, { 3, 1 } };
    int N = A.GetLength(0);
 
    // Function Call
    Console.Write(longestSubSequence(A, N));
}
}
 
// This code is contributed by target_2.

Javascript

<script>
 
// JavaScript program for the above approach
 
 
// Function to find the length of the
// longest subsequence of pairs whose first
// element is increasing and second is decreasing
function longestSubSequence(A, N)
{
    // dp[i]: Stores the longest
    // subsequence upto i
    let dp = new Array(N);
    for (let i = 0; i < N; i++) {
 
        // Base case
        dp[i] = 1;
 
        for (let j = 0; j < i; j++) {
 
            // When the conditions hold
            if (A[j][0] < A[i][0]
                && A[j][1] > A[i][1]) {
 
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
 
    // Finally, print the required answer
    document.write(dp[N - 1] + "<br>");
}
 
// Driver Code
 
    // Given Input
    let A = [ [ 1, 2 ],
            [ 2, 2 ],
            [ 3, 1 ] ];
 
    let N = A.length;
 
    // Function Call
    longestSubSequence(A, N);
     
</script>
Producción: 

2

 

Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)

Enfoque eficiente: este problema tiene la propiedad de subproblemas superpuestos y la propiedad de subestructura óptima . Por lo tanto, este problema se puede resolver utilizando Programación Dinámica . Al igual que otros problemas típicos de Programación Dinámica ( DP ), se puede evitar el recálculo de los mismos subproblemas construyendo una array temporal que almacene los resultados de los subproblemas. 

Siga los pasos a continuación para resolver este problema: 

  • Inicialice una array dp[] , donde dp[i] almacena la longitud de la subsecuencia más larga que se puede formar utilizando elementos hasta el índice i .
  • Iterar sobre el rango [0, N-1] usando una variable i : 
    • Caso base: actualice dp[i] como 1.
    • Iterar sobre el rango [0, i – 1] usando una variable j :
      •  Si A[j].primero es menor que A[i].primero y A[j].segundo es mayor que A[i].segundo, entonces actualice dp[i] como máximo de dp[i] y dp[j ] + 1.
    • Finalmente, imprima dp[N-1] .

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length of the
// longest subsequence of pairs whose first
// element is increasing and second is decreasing
void longestSubSequence(pair<int, int> A[], int N)
{
    // dp[i]: Stores the longest
    // subsequence upto i
    int dp[N];
    for (int i = 0; i < N; i++) {
 
        // Base case
        dp[i] = 1;
 
        for (int j = 0; j < i; j++) {
 
            // When the conditions hold
            if (A[j].first < A[i].first
                && A[j].second > A[i].second) {
 
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
 
    // Finally, print the required answer
    cout << dp[N - 1] << endl;
}
 
// Driver Code
int main()
{
    // Given Input
    pair<int, int> A[] = { { 1, 2 },
                           { 2, 2 },
                           { 3, 1 } };
 
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function Call
    longestSubSequence(A, N);
 
    return 0;
}

Java

// Java program for the above approach
class GFG{
     
// Function to find the length of the
// longest subsequence of pairs whose first
// element is increasing and second is decreasing
public static void longestSubSequence(int[][] A, int N)
{
     
    // dp[i]: Stores the longest
    // subsequence upto i
    int[] dp = new int[N];
     
    for(int i = 0; i < N; i++)
    {
         
        // Base case
        dp[i] = 1;
 
        for(int j = 0; j < i; j++)
        {
             
            // When the conditions hold
            if (A[j][0] < A[i][0] && A[j][1] > A[i][1])
            {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
 
    // Finally, print the required answer
    System.out.println(dp[N - 1]);
}
 
// Driver Code
public static void main(String args[])
{
     
    // Given Input
    int[][] A = { { 1, 2 },
                  { 2, 2 },
                  { 3, 1 } };
 
    int N = A.length;
 
    // Function Call
    longestSubSequence(A, N);
}
}
 
// This code is contributed by gfgking

Python3

# Python3 program for the above approach
 
# Function to find the length of the
# longest subsequence of pairs whose first
# element is increasing and second is decreasing
def longestSubSequence(A, N):
   
    # dp[i]: Stores the longest
    # subsequence upto i
    dp = [0]*N
    for i in range(N):
       
        # Base case
        dp[i] = 1
 
        for j in range(i):
           
            # When the conditions hold
            if (A[j][0] < A[i][0] and A[j][1] > A[i][1]):
                dp[i] = max(dp[i], dp[j] + 1)
 
 
    # Finally, print the required answer
    print (dp[N - 1])
 
# Driver Code
if __name__ == '__main__':
   
    #Given Input
    A = [ [ 1, 2 ],
           [ 2, 2 ],
           [ 3, 1 ] ]
 
    N = len(A)
 
    #Function Call
    longestSubSequence(A, N)
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
class GFG {
     
    // Function to find the length of the
    // longest subsequence of pairs whose first
    // element is increasing and second is decreasing
    static void longestSubSequence(int[,] A, int N)
    {
          
        // dp[i]: Stores the longest
        // subsequence upto i
        int[] dp = new int[N];
          
        for(int i = 0; i < N; i++)
        {
              
            // Base case
            dp[i] = 1;
      
            for(int j = 0; j < i; j++)
            {
                  
                // When the conditions hold
                if (A[j,0] < A[i,0] && A[j,1] > A[i,1])
                {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }
      
        // Finally, print the required answer
        Console.Write(dp[N - 1]);
    }
 
  static void Main()
  {
     
    // Given Input
    int[,] A = { { 1, 2 },
                  { 2, 2 },
                  { 3, 1 } };
  
    int N = A.GetLength(0);
  
    // Function Call
    longestSubSequence(A, N);
  }
}
 
// This code is contributed by decode2207.

Javascript

<script>
 
// JavaScript program for the above approach
 
 
// Function to find the length of the
// longest subsequence of pairs whose first
// element is increasing and second is decreasing
function longestSubSequence(A, N) {
    // dp[i]: Stores the longest
    // subsequence upto i
    let dp = new Array(N);
    for (let i = 0; i < N; i++) {
 
        // Base case
        dp[i] = 1;
 
        for (let j = 0; j < i; j++) {
 
            // When the conditions hold
            if (A[j][0] < A[i][0]
                && A[j][1] > A[i][1]) {
 
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
 
    // Finally, print the required answer
    document.write(dp[N - 1] + "<br>");
}
 
// Driver Code
 
// Given Input
let A = [[1, 2],
[2, 2],
[3, 1]];
 
let N = A.length;
 
// Function Call
longestSubSequence(A, N);
 
</script>
Producción: 

2

 

Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por shekabhi1208 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 *