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