Dada una array arr[] que consta de N elementos únicos, la tarea es generar una array B[] de longitud N tal que B[i] sea el número de subsecuencias en las que arr[i] es el elemento máximo.
Ejemplos:
Entrada: arr[] = {2, 3, 1}
Salida: {2, 4, 1}
Explicación: Las subsecuencias en las que arr[0] ( = 2) es máximo son {2}, {2, 1}.
Las subsecuencias en las que arr[1] ( = 3) es máximo son {3}, {1, 3, 2}, {2, 3}, {1, 3}.
La subsecuencia en la que arr[2] ( = 1) es máxima es {1}.Entrada: arr[] = {23, 34, 12, 7, 15, 31}
Salida: {8, 32, 2, 1, 4, 16}
Enfoque: El problema se puede resolver observando que todas las subsecuencias en las que un elemento, arr[i] , aparecerá como máximo, contendrán todos los elementos menores que arr[i] . Por lo tanto, el número total de subsecuencias distintas será 2 (Número de elementos menores que arr[i]) . Siga los pasos a continuación para resolver el problema:
- Ordene los índices de la array arr[] con respecto a sus valores correspondientes presentes en la array dada y almacene esos índices en la array indices[] , donde arr[indices[i]] < arr[indices[i+1]] .
- Inicialice un número entero, subseq con 1 para almacenar el número de subsecuencias posibles.
- Iterar N veces con el puntero sobre el rango [0, N-1] usando una variable, i .
- B[índices[i]] es el número de subsecuencias en las que arr[índices[i]] es máximo, es decir, 2 i , ya que habrá i elementos menos que arr[índices[i]].
- Guarde la respuesta para B[indices[i]] como B[indices[i]] = subseq .
- Actualice subseq multiplicándolo por 2 .
- Imprime los elementos de la array B[] como respuesta.
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 merge the subarrays
// arr[l .. m] and arr[m + 1, .. r]
// based on indices[]
void merge(int* indices, int* a, int l,
int mid, int r)
{
int temp_ind[r - l + 1], j = mid + 1;
int i = 0, temp_l = l, k;
while (l <= mid && j <= r) {
// If a[indices[l]] is less than
// a[indices[j]], add indice[l] to temp
if (a[indices[l]] < a[indices[j]])
temp_ind[i++] = indices[l++];
// Else add indices[j]
else
temp_ind[i++] = indices[j++];
}
// Add remaining elements
while (l <= mid)
temp_ind[i++] = indices[l++];
// Add remainging elements
while (j <= r)
temp_ind[i++] = indices[j++];
for (k = 0; k < i; k++)
indices[temp_l++] = temp_ind[k];
}
// Recursive function to divide
// the array into to parts
void divide(int* indices, int* a, int l, int r)
{
if (l >= r)
return;
int mid = l / 2 + r / 2;
// Recursive call for elements before mid
divide(indices, a, l, mid);
// Recursive call for elements after mid
divide(indices, a, mid + 1, r);
// Merge the two sorted arrays
merge(indices, a, l, mid, r);
}
// Function to find the number of
// subsequences for each element
void noOfSubsequences(int arr[], int N)
{
int indices[N], i;
for (i = 0; i < N; i++)
indices[i] = i;
// Sorting the indices according
// to array arr[]
divide(indices, arr, 0, N - 1);
// Array to store output numbers
int B[N];
// Initialize subseq
int subseq = 1;
for (i = 0; i < N; i++) {
// B[i] is 2^i
B[indices[i]] = subseq;
// Doubling the subsequences
subseq *= 2;
}
// Print the final output, array B[]
for (i = 0; i < N; i++)
cout << B[i] << " ";
}
// Driver Code
int main()
{
// Given array
int arr[] = { 2, 3, 1 };
// Given length
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
noOfSubsequences(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to merge the subarrays
// arr[l .. m] and arr[m + 1, .. r]
// based on indices[]
static void merge(int[] indices, int[] a, int l,
int mid, int r)
{
int []temp_ind = new int[r - l + 1];
int j = mid + 1;
int i = 0, temp_l = l, k;
while (l <= mid && j <= r)
{
// If a[indices[l]] is less than
// a[indices[j]], add indice[l] to temp
if (a[indices[l]] < a[indices[j]])
temp_ind[i++] = indices[l++];
// Else add indices[j]
else
temp_ind[i++] = indices[j++];
}
// Add remaining elements
while (l <= mid)
temp_ind[i++] = indices[l++];
// Add remainging elements
while (j <= r)
temp_ind[i++] = indices[j++];
for(k = 0; k < i; k++)
indices[temp_l++] = temp_ind[k];
}
// Recursive function to divide
// the array into to parts
static void divide(int[] indices, int[] a,
int l, int r)
{
if (l >= r)
return;
int mid = l / 2 + r / 2;
// Recursive call for elements before mid
divide(indices, a, l, mid);
// Recursive call for elements after mid
divide(indices, a, mid + 1, r);
// Merge the two sorted arrays
merge(indices, a, l, mid, r);
}
// Function to find the number of
// subsequences for each element
static void noOfSubsequences(int arr[], int N)
{
int []indices = new int[N];
int i;
for(i = 0; i < N; i++)
indices[i] = i;
// Sorting the indices according
// to array arr[]
divide(indices, arr, 0, N - 1);
// Array to store output numbers
int[] B = new int[N];
// Initialize subseq
int subseq = 1;
for(i = 0; i < N; i++)
{
// B[i] is 2^i
B[indices[i]] = subseq;
// Doubling the subsequences
subseq *= 2;
}
// Print the final output, array B[]
for(i = 0; i < N; i++)
System.out.print(B[i] + " ");
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 2, 3, 1 };
// Given length
int N = arr.length;
// Function call
noOfSubsequences(arr, N);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program for the above approach # Function to merge the subarrays # arr[l .. m] and arr[m + 1, .. r] # based on indices[] def merge(indices, a, l, mid, r): temp_ind = [0] * (r - l + 1) j = mid + 1 i = 0 temp_l = l while (l <= mid and j <= r): # If a[indices[l]] is less than # a[indices[j]], add indice[l] to temp if (a[indices[l]] < a[indices[j]]): temp_ind[i] = indices[l] i += 1 l += 1 # Else add indices[j] else: temp_ind[i] = indices[j] i += 1 j += 1 # Add remaining elements while (l <= mid): temp_ind[i] = indices[l] i += 1 l += 1 # Add remainging elements while (j <= r): temp_ind[i] = indices[j] i += 1 j += 1 for k in range(i): indices[temp_l] = temp_ind[k] temp_l += 1 # Recursive function to divide # the array into to parts def divide(indices, a, l, r): if (l >= r): return mid = l // 2 + r // 2 # Recursive call for elements # before mid divide(indices, a, l, mid) # Recursive call for elements # after mid divide(indices, a, mid + 1, r) # Merge the two sorted arrays merge(indices, a, l, mid, r) # Function to find the number of # subsequences for each element def noOfSubsequences(arr, N): indices = N * [0] for i in range(N): indices[i] = i # Sorting the indices according # to array arr[] divide(indices, arr, 0, N - 1) # Array to store output numbers B = [0] * N # Initialize subseq subseq = 1 for i in range(N): # B[i] is 2^i B[indices[i]] = subseq # Doubling the subsequences subseq *= 2 # Print the final output, array B[] for i in range(N): print(B[i], end = " ") # Driver Code if __name__ == "__main__": # Given array arr = [ 2, 3, 1 ] # Given length N = len(arr) # Function call noOfSubsequences(arr, N) # This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
class GFG{
// Function to merge the subarrays
// arr[l .. m] and arr[m + 1, .. r]
// based on indices[]
static void merge(int[] indices, int[] a, int l,
int mid, int r)
{
int []temp_ind = new int[r - l + 1];
int j = mid + 1;
int i = 0, temp_l = l, k;
while (l <= mid && j <= r)
{
// If a[indices[l]] is less than
// a[indices[j]], add indice[l] to temp
if (a[indices[l]] < a[indices[j]])
temp_ind[i++] = indices[l++];
// Else add indices[j]
else
temp_ind[i++] = indices[j++];
}
// Add remaining elements
while (l <= mid)
temp_ind[i++] = indices[l++];
// Add remainging elements
while (j <= r)
temp_ind[i++] = indices[j++];
for(k = 0; k < i; k++)
indices[temp_l++] = temp_ind[k];
}
// Recursive function to divide
// the array into to parts
static void divide(int[] indices, int[] a,
int l, int r)
{
if (l >= r)
return;
int mid = l / 2 + r / 2;
// Recursive call for elements before mid
divide(indices, a, l, mid);
// Recursive call for elements after mid
divide(indices, a, mid + 1, r);
// Merge the two sorted arrays
merge(indices, a, l, mid, r);
}
// Function to find the number of
// subsequences for each element
static void noOfSubsequences(int []arr, int N)
{
int []indices = new int[N];
int i;
for(i = 0; i < N; i++)
indices[i] = i;
// Sorting the indices according
// to array []arr
divide(indices, arr, 0, N - 1);
// Array to store output numbers
int[] B = new int[N];
// Initialize subseq
int subseq = 1;
for(i = 0; i < N; i++)
{
// B[i] is 2^i
B[indices[i]] = subseq;
// Doubling the subsequences
subseq *= 2;
}
// Print the readonly output, array []B
for(i = 0; i < N; i++)
Console.Write(B[i] + " ");
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []arr = { 2, 3, 1 };
// Given length
int N = arr.Length;
// Function call
noOfSubsequences(arr, N);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program for the above approach
// Function to merge the subarrays
// arr[l .. m] and arr[m + 1, .. r]
// based on indices[]
function merge(indices, a, l, mid, r)
{
let temp_ind = [];
let j = mid + 1;
let i = 0, temp_l = l, k;
while (l <= mid && j <= r)
{
// If a[indices[l]] is less than
// a[indices[j]], add indice[l] to temp
if (a[indices[l]] < a[indices[j]])
temp_ind[i++] = indices[l++];
// Else add indices[j]
else
temp_ind[i++] = indices[j++];
}
// Add remaining elements
while (l <= mid)
temp_ind[i++] = indices[l++];
// Add remainging elements
while (j <= r)
temp_ind[i++] = indices[j++];
for(k = 0; k < i; k++)
indices[temp_l++] = temp_ind[k];
}
// Recursive function to divide
// the array leto to parts
function divide(indices, a, l, r)
{
if (l >= r)
return;
let mid = l / 2 + r / 2;
// Recursive call for elements before mid
divide(indices, a, l, mid);
// Recursive call for elements after mid
divide(indices, a, mid + 1, r);
// Merge the two sorted arrays
merge(indices, a, l, mid, r);
}
// Function to find the number of
// subsequences for each element
function noOfSubsequences(arr, N)
{
let indices = [];
let i;
for(i = 0; i < N; i++)
indices[i] = i;
// Sorting the indices according
// to array arr[]
divide(indices, arr, 0, N - 1);
// Array to store output numbers
let B = [];
// Initialize subseq
let subseq = 1;
for(i = 0; i < N; i++)
{
// B[i] is 2^i
B[indices[i]] = subseq;
// Doubling the subsequences
subseq *= 2;
}
// Print the final output, array B[]
for(i = 0; i < N; i++)
document.write(B[i] + " ");
}
// Driver code
// Given array
let arr = [ 2, 3, 1 ];
// Given length
let N = arr.length;
// Function call
noOfSubsequences(arr, N);
// This code is contributed by avijitmondal1998
</script>
Producción:
2 4 1
Complejidad de tiempo: O(NlogN) donde N es la longitud de la array dada.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA