Te dan n pares de números. En cada par, el primer número siempre es más pequeño que el segundo número. Un par (c, d) puede seguir a otro par (a, b) si b < c. La string de pares se puede formar de esta manera. Encuentre la string más larga que se puede formar a partir de un conjunto dado de pares.
Fuente: Amazon Entrevista | Conjunto 2
Por ejemplo, si los pares dados son {{5, 24}, {39, 60}, {15, 28}, {27, 40}, {50, 90} }, entonces la string más larga que se puede formar es de longitud 3, y la string es {{5, 24}, {27, 40}, {50, 90}}
Este problema es una variación del problema estándar de subsecuencia creciente más larga . El siguiente es un proceso simple de dos pasos.
1) Clasifique los pares dados en orden creciente del primer (o más pequeño) elemento. ¿Por qué necesitamos clasificar? Considere el ejemplo {{6, 8}, {3, 4}} para comprender la necesidad de ordenar. Si procedemos al segundo paso sin clasificar, obtenemos el resultado 1. Pero el resultado correcto es 2.
2) Ahora ejecute un proceso LIS modificado en el que comparemos el segundo elemento del LIS ya finalizado con el primer elemento del nuevo LIS que se está construyendo.
El siguiente código es una ligera modificación del método 2 de esta publicación .
C++
// CPP program for above approach
#include <bits/stdc++.h>
using namespace std;
// Structure for a Pair
class Pair
{
public:
int a;
int b;
};
// This function assumes that arr[]
// is sorted in increasing order
// according the first
// (or smaller) values in Pairs.
int maxChainLength( Pair arr[], int n)
{
int i, j, max = 0;
int *mcl = new int[sizeof( int ) * n ];
/* Initialize MCL (max chain length)
values for all indexes */
for ( i = 0; i < n; i++ )
mcl[i] = 1;
/* Compute optimized chain
length values in bottom up manner */
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if ( arr[i].a > arr[j].b &&
mcl[i] < mcl[j] + 1)
mcl[i] = mcl[j] + 1;
// mcl[i] now stores the maximum
// chain length ending with Pair i
/* Pick maximum of all MCL values */
for ( i = 0; i < n; i++ )
if ( max < mcl[i] )
max = mcl[i];
/* Free memory to avoid memory leak */
return max;
}
/* Driver code */
int main()
{
Pair arr[] = { {5, 24}, {15, 25},
{27, 40}, {50, 60} };
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Length of maximum size chain is "
<< maxChainLength( arr, n );
return 0;
}
// This code is contributed by rathbhupendra
C
#include<stdio.h>
#include<stdlib.h>
// Structure for a pair
struct pair
{
int a;
int b;
};
// This function assumes that
// arr[] is sorted in increasing order
// according the first
// (or smaller) values in pairs.
int maxChainLength( struct pair arr[], int n)
{
int i, j, max = 0;
int *mcl = (int*) malloc ( sizeof( int ) * n );
/* Initialize MCL (max chain
length) values for all indexes */
for ( i = 0; i < n; i++ )
mcl[i] = 1;
/* Compute optimized chain length
values in bottom up manner */
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if ( arr[i].a > arr[j].b &&
mcl[i] < mcl[j] + 1)
mcl[i] = mcl[j] + 1;
// mcl[i] now stores the maximum
// chain length ending with pair i
/* Pick maximum of all MCL values */
for ( i = 0; i < n; i++ )
if ( max < mcl[i] )
max = mcl[i];
/* Free memory to avoid memory leak */
free( mcl );
return max;
}
/* Driver program to test above function */
int main()
{
struct pair arr[] = { {5, 24}, {15, 25},
{27, 40}, {50, 60} };
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of maximum size chain is %d\n",
maxChainLength( arr, n ));
return 0;
}
Java
// Java program for above approach
class Pair
{
int a;
int b;
public Pair(int a, int b)
{
this.a = a;
this.b = b;
}
// This function assumes that
// arr[] is sorted in increasing order
// according the first (or smaller)
// values in pairs.
static int maxChainLength(Pair arr[], int n)
{
int i, j, max = 0;
int mcl[] = new int[n];
/* Initialize MCL (max chain length)
values for all indexes */
for ( i = 0; i < n; i++ )
mcl[i] = 1;
/* Compute optimized chain length
values in bottom up manner */
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if ( arr[i].a > arr[j].b &&
mcl[i] < mcl[j] + 1)
mcl[i] = mcl[j] + 1;
// mcl[i] now stores the maximum
// chain length ending with pair i
/* Pick maximum of all MCL values */
for ( i = 0; i < n; i++ )
if ( max < mcl[i] )
max = mcl[i];
return max;
}
/* Driver program to test above function */
public static void main(String[] args)
{
Pair arr[] = new Pair[]
{
new Pair(5,24),
new Pair(15, 25),
new Pair (27, 40),
new Pair(50, 60)};
System.out.println("Length of maximum
size chain is " +
maxChainLength(arr, arr.length));
}
}
Python3
# Python program for above approach
class Pair(object):
def __init__(self, a, b):
self.a = a
self.b = b
# This function assumes
# that arr[] is sorted in increasing
# order according the
# first (or smaller) values in pairs.
def maxChainLength(arr, n):
max = 0
# Initialize MCL(max chain
# length) values for all indices
mcl = [1 for i in range(n)]
# Compute optimized chain
# length values in bottom up manner
for i in range(1, n):
for j in range(0, i):
if (arr[i].a > arr[j].b and
mcl[i] < mcl[j] + 1):
mcl[i] = mcl[j] + 1
# mcl[i] now stores the maximum
# chain length ending with pair i
# Pick maximum of all MCL values
for i in range(n):
if (max < mcl[i]):
max = mcl[i]
return max
# Driver program to test above function
arr = [Pair(5, 24), Pair(15, 25),
Pair(27, 40), Pair(50, 60)]
print('Length of maximum size chain is',
maxChainLength(arr, len(arr)))
# This code is contributed by Soumen Ghosh
C#
// Dynamic C# program to find
// Maximum Length Chain of Pairs
using System;
class Pair
{
int a;
int b;
public Pair(int a, int b)
{
this.a = a;
this.b = b;
}
// This function assumes that arr[]
// is sorted in increasing order
// according the first (or smaller)
// values in pairs.
static int maxChainLength(Pair []arr, int n)
{
int i, j, max = 0;
int []mcl = new int[n];
// Initialize MCL (max chain length)
// values for all indexes
for(i = 0; i < n; i++ )
mcl[i] = 1;
// Compute optimized chain length
// values in bottom up manner
for(i = 1; i < n; i++)
for (j = 0; j < i; j++)
if(arr[i].a > arr[j].b &&
mcl[i] < mcl[j] + 1)
// mcl[i] now stores the maximum
// chain length ending with pair i
mcl[i] = mcl[j] + 1;
// Pick maximum of all MCL values
for ( i = 0; i < n; i++ )
if (max < mcl[i] )
max = mcl[i];
return max;
}
// Driver Code
public static void Main()
{
Pair []arr = new Pair[]
{new Pair(5,24), new Pair(15, 25),
new Pair (27, 40), new Pair(50, 60)};
Console.Write("Length of maximum size
chain is " +
maxChainLength(arr, arr.Length));
}
}
// This code is contributed by nitin mittal.
Javascript
<script>
// Javascript program for above approach
class Pair
{
constructor(a,b)
{
this.a=a;
this.b=b;
}
}
// This function assumes that
// arr[] is sorted in increasing order
// according the first (or smaller)
// values in pairs.
function maxChainLength(arr,n)
{
let i, j, max = 0;
let mcl = new Array(n);
/* Initialize MCL (max chain length)
values for all indexes */
for ( i = 0; i < n; i++ )
mcl[i] = 1;
/* Compute optimized chain length
values in bottom up manner */
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if ( arr[i].a > arr[j].b &&
mcl[i] < mcl[j] + 1)
mcl[i] = mcl[j] + 1;
// mcl[i] now stores the maximum
// chain length ending with pair i
/* Pick maximum of all MCL values */
for ( i = 0; i < n; i++ )
if ( max < mcl[i] )
max = mcl[i];
return max;
}
/* Driver program to test above function */
let arr=[ new Pair(5,24),
new Pair(15, 25),
new Pair (27, 40),
new Pair(50, 60)];
document.write("Length of maximum size chain is " +
maxChainLength(arr, arr.length));
// This code is contributed by avanitrachhadiya2155
</script>
C++14
// CPP program for above approach
#include <bits/stdc++.h>
using namespace std;
// Structure val
struct val
{
int first;
int second;
};
map<pair<int, int>, int> m;
// Memoisation function
int findMaxChainLen(struct val p[], int n,
int prev, int pos)
{
// Check if pair { pos, prev } exists
// in m
if (m.find({ pos, prev }) != m.end())
{
return m[{ pos, prev }];
}
// Check if pos is >=n
if (pos >= n)
return 0;
// Check if p[pos].first is
// less than prev
if (p[pos].first <= prev)
{
return findMaxChainLen(p, n, prev,
pos + 1);
}
else
{
int ans = max(findMaxChainLen(p, n,
p[pos].second, 0) + 1,
findMaxChainLen(p, n,
prev, pos + 1));
m[{ pos, prev }] = ans;
return ans;
}
}
// Function to calculate maximum
// chain length
int maxChainLen(struct val p[], int n)
{
m.clear();
// Call memoisation function
int ans = findMaxChainLen(p, n, 0, 0);
return ans;
}
// Driver Code
int main()
{
int n = 5;
val p[n];
p[0].first = 5;
p[0].second = 24;
p[1].first = 39;
p[1].second = 60;
p[2].first = 15;
p[2].second = 28;
p[3].first = 27;
p[3].second = 40;
p[4].first = 50;
p[4].second = 90;
// Function Call
cout << maxChainLen(p, n) << endl;
return 0;
}
Java
// Java program for above approach
import java.util.*;
class GFG{
// Structure val
static class val
{
int first;
int second;
};
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
@Override
public int hashCode()
{
final int prime = 31;
int result = 1;
result = prime * result + first;
result = prime * result + second;
return result;
}
@Override
public boolean equals(Object obj)
{
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
pair other = (pair) obj;
if (first != other.first)
return false;
if (second != other.second)
return false;
return true;
}
}
static Map<pair, Integer> m = new HashMap<>();
// Memoisation function
static int findMaxChainLen(val p[], int n,
int prev, int pos)
{
// Check if pair { pos, prev } exists
// in m
if (m.containsKey(new pair(pos, prev)))
{
return m.get(new pair(pos, prev));
}
// Check if pos is >=n
if (pos >= n)
return 0;
// Check if p[pos].first is
// less than prev
if (p[pos].first <= prev)
{
return findMaxChainLen(p, n, prev,
pos + 1);
}
else
{
int ans = Math.max(findMaxChainLen(
p, n, p[pos].second, 0) + 1,
findMaxChainLen(
p, n, prev, pos + 1));
m.put(new pair(pos, prev), ans);
return ans;
}
}
// Function to calculate maximum
// chain length
static int maxChainLen(val p[], int n)
{
m.clear();
// Call memoisation function
int ans = findMaxChainLen(p, n, 0, 0);
return ans;
}
// Driver Code
public static void main(String[] args)
{
int n = 5;
val []p = new val[n];
for(int i = 0; i < n; i++)
p[i] = new val();
p[0].first = 5;
p[0].second = 24;
p[1].first = 39;
p[1].second = 60;
p[2].first = 15;
p[2].second = 28;
p[3].first = 27;
p[3].second = 40;
p[4].first = 50;
p[4].second = 90;
// Function Call
System.out.print(maxChainLen(p, n) + "\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program for above approach
# Structure val
class val:
def __init__(self,first,second):
self.first = first
self.second = second
# Memoisation function
def findMaxChainLen(p, n, prev, pos):
global m
# Check if pair { pos, prev } exists
# in m
if (val(pos, prev) in m):
return m[val(pos, prev)]
# Check if pos is >=n
if (pos >= n):
return 0
# Check if p[pos].first is
# less than prev
if (p[pos].first <= prev):
return findMaxChainLen(p, n, prev, pos + 1)
else:
ans = max(findMaxChainLen(p, n,
p[pos].second, 0) + 1,
findMaxChainLen(p, n,
prev, pos + 1))
m[val(pos, prev)] = ans
return ans
# Function to calculate maximum
# chain length
def maxChainLen(p,n):
global m
m.clear()
# Call memoisation function
ans = findMaxChainLen(p, n, 0, 0)
return ans
# Driver Code
n = 5
p = [0]*n
p[0] = val(5,24)
p[1] = val(39,60)
p[2] = val(15,28)
p[3] = val(27,40)
p[4] = val(50,90)
m = {}
# Function Call
print(maxChainLen(p, n))
# This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript program for above approach
// Structure val
class val
{
constructor(first,second){
this.first = first;
this.second = second;
}
};
let m = new Map();
// Memoisation function
function findMaxChainLen(p,n,prev,pos)
{
// Check if pair { pos, prev } exists
// in m
if (m.has(new val(pos, prev)))
return m.get(new val(pos, prev));
// Check if pos is >=n
if (pos >= n)
return 0;
// Check if p[pos].first is
// less than prev
if (p[pos].first <= prev)
{
return findMaxChainLen(p, n, prev,
pos + 1);
}
else
{
let ans = Math.max(findMaxChainLen(p, n,
p[pos].second, 0) + 1,
findMaxChainLen(p, n,
prev, pos + 1));
m.set(new val(pos, prev),ans);
return ans;
}
}
// Function to calculate maximum
// chain length
function maxChainLen(p,n)
{
m.clear();
// Call memoisation function
let ans = findMaxChainLen(p, n, 0, 0);
return ans;
}
// Driver Code
let n = 5;
let p = new Array(n);
p[0] = new val(5,24);
p[1] = new val(39,60);
p[2] = new val(15,28);
p[3] = new val(27,40);
p[4] = new val(50,90);
// Function Call
document.write(maxChainLen(p, n),"</br>");
// code is contributed by shinjanpatra
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA