Dadas dos arrays arr1[] y arr2[] de longitud M y N que consisten en dígitos [0, 9] que representan dos números y un número entero K ( K ≤ M + N ), la tarea es encontrar el número máximo de K dígitos posible seleccionando subsecuencias de las arrays dadas de modo que el orden relativo de los dígitos sea el mismo que en la array dada.
Ejemplos:
Entrada: arr1[] = {3, 4, 6, 5}, arr2[] = {9, 1, 2, 5, 8, 3}, K = 5
Salida: 98653
Explicación: El número máximo que se puede formar de las arrays dadas arr1[] y arr2[] de longitud K es 98653.Entrada: arr1[] = {6, 7}, arr2[] = {6, 0, 4}, K = 5
Salida: 67604
Explicación: El número máximo que se puede formar a partir de las arrays dadas arr1[] y arr2[ ] de longitud K es 67604.
Enfoque ingenuo: la idea es generar todas las subsecuencias de longitud s1 de arr1[] y todas las subsecuencias de longitud (K – s1) de la array arr2[] sobre todos los valores de s1 en el rango [0, K] y realizar un seguimiento de el número máximo así formado al fusionar ambas arrays en cada iteración.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es obtener el número máximo de la array arr1[] y de longitud s1 y el número máximo de la array arr2[] y de longitud (K – s1) . Luego, combine las dos arrays para obtener el número máximo de longitud K . Siga los pasos a continuación para resolver el problema dado:
- Iterar sobre el rango [0, K] usando la variable i y generar todas las posibles subsecuencias decrecientes de longitud i conservando el mismo orden que en la array arr1[] y las subsecuencias de longitud (K – i) siguiendo el mismo orden que en la array arr2[] .
- Para generar una subsecuencia decreciente de longitud L de cualquier array arr[] en el paso anterior, haga lo siguiente:
- Inicialice una array ans[] para almacenar las subsecuencias de longitud L conservando el mismo orden que en arr[] y recorra la array arr[] y haga lo siguiente:
- Hasta que el último elemento sea menor que el elemento actual, elimine el último elemento de la array ans[] .
- Si la longitud de ans[] es menor que L , inserte el elemento actual en ans[] .
- Después de los pasos anteriores, la array ans[] en la subsecuencia resultante.
- Inicialice una array ans[] para almacenar las subsecuencias de longitud L conservando el mismo orden que en arr[] y recorra la array arr[] y haga lo siguiente:
- Mientras genera las subsecuencias de toda la longitud posible en el Paso 1 utilizando el enfoque discutido en el Paso 2 , genere el número máximo fusionando las dos subsecuencias formadas.
- Después de los pasos anteriores, imprima esa subsecuencia que da el número máximo después de la fusión.
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;
void pop_front(std::vector<int> &v)
{
if (v.size() > 0) {
v.erase(v.begin());
}
}
// Function to calculate maximum
// number from nums of length c_len
vector<int> helper(vector<int> nums, int c_len)
{
// Store the resultant maximum
vector<int> ans;
// Length of the nums array
int ln = nums.size();
// Traverse the nums array
for(int i=0;i<ln;i++)
{
while(ans.size()>0 && ans.back()<nums[i] && ((ln-i) > (c_len-ans.size())))
// If true, then pop
// out the last element
ans.pop_back();
// Check the length with
// required length
if(ans.size()<c_len)
// Append the value to ans
ans.push_back(nums[i]);
}
// Return the ans
return ans;
}
// Function to find maximum K-digit number
// possible from subsequences of the
// two arrays nums1[] and nums2[]
vector<int> maxNumber(vector<int> nums1, vector<int> nums2,int k)
{
// Store lengths of the arrays
int l1 = nums1.size();
int l2 = nums2.size();
// Store the resultant subsequence
vector<int> rs;
// Traverse and pick the maximum
for(int s1=max(0, k-l2);s1<=min(k, l1);s1++)
{
// p1 and p2 stores maximum number possible
// of length s1 and k - s1 from
// the arrays nums1[] & nums2[]
vector<int> p1,p2;
p1 = helper(nums1, s1);
p2 = helper(nums2, k-s1);
// Update the maximum number
vector<int> temp;
for(int j=0;j<k;j++)
{
vector<int> temp2 = max(p1,p2);
int fr = temp2.front();
if(p1>p2)
pop_front(p1);
else
pop_front(p2);
temp.push_back(fr);
}
rs = max(rs, temp);
}
// Return the result
return rs;
}
// Driver Code
int main()
{
vector<int> arr1{3, 4, 6, 5};
vector<int> arr2{9, 1, 2, 5, 8, 3};
int K=5;
// Function Call
vector<int> v = maxNumber(arr1, arr2, K);
for(int i=0;i<v.size();i++)
cout<<v[i]<<" ";
return 0;
}
// This code is contributed by Pushpesh Raj
Java
import java.util.*;
import java.io.*;
// Java program for the above approach
class GFG{
// Function to calculate maximum
// number from nums of length c_len
static ArrayList<Integer> helper(ArrayList<Integer> nums, int c_len)
{
// Store the resultant maximum
ArrayList<Integer> ans = new ArrayList<Integer>();
// Length of the nums array
int ln = nums.size();
// Traverse the nums array
for(int i = 0 ; i < ln ; i++)
{
while(ans.size() > 0 && ans.get(ans.size() - 1) < nums.get(i) && ((ln-i) > (c_len - ans.size()))){
// If true, then pop
// out the last element
ans.remove(ans.size() - 1);
}
// Check the length with
// required length
if(ans.size() < c_len){
// Append the value to ans
ans.add(nums.get(i));
}
}
// Return the ans
return ans;
}
// Returns True if a1 is greater than a2
static boolean comp(ArrayList<Integer> a1, ArrayList<Integer> a2){
int s1 = a1.size();
int s2 = a2.size();
int i1 = 0, i2 = 0;
while(i1 < s1 && i2 < s2){
if(a1.get(i1) > a2.get(i2)){
return true;
}else if(a1.get(i1) < a2.get(i2)){
return false;
}
i1++;
i2++;
}
if(i1 < s1) return true;
return false;
}
// Function to find maximum K-digit number
// possible from subsequences of the
// two arrays nums1[] and nums2[]
static ArrayList<Integer> maxNumber(ArrayList<Integer> nums1, ArrayList<Integer> nums2,int k)
{
// Store lengths of the arrays
int l1 = nums1.size();
int l2 = nums2.size();
// Store the resultant subsequence
ArrayList<Integer> rs = new ArrayList<Integer>();
// Traverse and pick the maximum
for(int s1 = Math.max(0, k-l2) ; s1 <= Math.min(k, l1) ; s1++)
{
// p1 and p2 stores maximum number possible
// of length s1 and k - s1 from
// the arrays nums1[] & nums2[]
ArrayList<Integer> p1 = new ArrayList<Integer>();
ArrayList<Integer> p2 = new ArrayList<Integer>();
p1 = helper(nums1, s1);
p2 = helper(nums2, k-s1);
// Update the maximum number
ArrayList<Integer> temp = new ArrayList<Integer>();
for(int j = 0 ; j < k ; j++)
{
ArrayList<Integer> temp2 = comp(p1, p2) ? p1 : p2;
int fr = temp2.get(0);
if(comp(p1, p2)){
if(p1.size() > 0){
p1.remove(0);
}
}else{
if(p2.size() > 0){
p2.remove(0);
}
}
temp.add(fr);
}
rs = comp(rs, temp) ? rs : temp;
}
// Return the result
return rs;
}
public static void main(String args[])
{
ArrayList<Integer> arr1 = new ArrayList<Integer>(
List.of(
3, 4, 6, 5
)
);
ArrayList<Integer> arr2 = new ArrayList<Integer>(
List.of(
9, 1, 2, 5, 8, 3
)
);
int K = 5;
// Function Call
ArrayList<Integer> v = maxNumber(arr1, arr2, K);
for(int i = 0 ; i < v.size() ; i++){
System.out.print(v.get(i) + " ");
}
}
}
// This code is contributed by subhamgoyal2014.
Python3
# Python program for the above approach # Function to find maximum K-digit number # possible from subsequences of the # two arrays nums1[] and nums2[] def maxNumber(nums1, nums2, k): # Store lengths of the arrays l1, l2 = len(nums1), len(nums2) # Store the resultant subsequence rs = [] # Function to calculate maximum # number from nums of length c_len def helper(nums, c_len): # Store the resultant maximum ans = [] # Length of the nums array ln = len(nums) # Traverse the nums array for idx, val in enumerate(nums): while ans and ans[-1] < val and ln-idx > c_len-len(ans): # If true, then pop # out the last element ans.pop(-1) # Check the length with # required length if len(ans) < c_len: # Append the value to ans ans.append(val) # Return the ans return ans # Traverse and pick the maximum for s1 in range(max(0, k-l2), min(k, l1)+1): # p1 and p2 stores maximum number possible # of length s1 and k - s1 from # the arrays nums1[] & nums2[] p1, p2 = helper(nums1, s1), helper(nums2, k-s1) # Update the maximum number rs = max(rs, [max(p1, p2).pop(0) for _ in range(k)]) # Return the result return rs # Driver Code arr1 = [3, 4, 6, 5] arr2 = [9, 1, 2, 5, 8, 3] K = 5 # Function Call print(maxNumber(arr1, arr2, K))
Producción:
[9, 8, 6, 5, 3]
Complejidad temporal: O(K*(M + N))
Espacio auxiliar: O(K)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA