Dadas dos arrays arr[] (indexación basada en 1) y queries[] que consisten en N enteros y queries[] contiene una permutación de los primeros N números naturales , la tarea es realizar la consulta en la array y encontrar la suma máxima de segmentos entre todos los segmentos formados de manera que en cada consulta consultas[ i] se elimina el elemento de array en las consultas de índice [i] y ese segmento se divide en 2 segmentos.
Ejemplos:
Entrada: arr[] = {1, 3, 2, 5}, queries[] = {3, 4, 1, 2}
Salida: 5 4 3 0
Explicación:
A continuación se muestran las consultas realizadas:
- Consulta 1: elimine el elemento en el índice 3, divida la array actual en {1, 3}, {5}. La suma máxima entre todos los segmentos es 5.
- Consulta 2: elimine el elemento en el índice 4, divida la array actual en {1, 3} {}. La suma máxima entre todos los segmentos es 4.
- Consulta 3: elimine el elemento en el índice 1, divida la array actual en {1}, {}. La suma máxima entre todos los segmentos es 1.
- Consulta 4: elimine el elemento en el índice 2, divida la array actual en {}, {}. La suma máxima entre todos los segmentos es 0.
Entrada: arr[] = {1, 2, 3, 4, 5}, consultas[] = {4, 2, 3, 5, 1}
Salida : 6 5 5 1 0
Enfoque: el problema dado se puede resolver utilizando la estructura de datos de unión de conjuntos disjuntos . La idea es almacenar todas las consultas en una array, inicialmente, todos los elementos están en diferentes conjuntos, procesar las consultas en orden inverso, para cada consulta realizar una operación de unión para el elemento actual con sus elementos del lado izquierdo y derecho usando la operación de búsqueda , realice un seguimiento paralelo del elemento máximo y luego guárdelo en una array, luego imprima los elementos de la array en el orden inverso. Siga los pasos a continuación para resolver el problema:
- Inicialice los vectores parent(N + 1) , rank(N + 1, 0) , setSum(N + 1, 0) y currMax .
- Iterar sobre el rango [1, N+1) usando la variable i y establecer el valor de parent[i] como -1 y setSum[i] como arr[i – 1] .
- Inserte el valor 0 en el vector currMax[] porque después de la última consulta, la respuesta será 0 .
- Iterar sobre el rango [N – 1, 0] en orden inverso usando la variable i y realizar los siguientes pasos:
- Si parent[queries[ I ]] es -1 , configúrelo como queries[i] .
- Si consultas[i] – 1 >= 0 && parent[consultas[i] – 1] != -1 , entonces llama a la operación de función union(parent, rank, setSum, queries[ I ], queries[I]-1) .
- Si consultas[i] + 1 <= N && parent[consultas[i] + 1] != -1, entonces llama a la operación de función union(parent, rank, setSum, queries[ I ], queries[I]+1) .
- Establezca el valor de maxAns como el máximo de maxAns o setSum[queries[ I ]] e inserte el valor de maxAns en el vector currMax[] .
- Invierta el vector currMax[] e imprima sus valores como respuesta.
A continuación se muestra la implementación del algoritmo anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Stores the maximum integer of the sets // for each query int maxAns = INT_MIN; // Function to perform the find operation // of disjoint set union int Find(vector<int>& parent, int a) { return parent[a] = (parent[a] == a) ? a : (Find( parent, parent[a])); } // Function to perform the Union operation // of disjoint set union void Union(vector<int>& parent, vector<int>& rank, vector<int>& setSum, int a, int b) { // Find the parent of a and b a = Find(parent, a); b = Find(parent, b); if (a == b) return; if (rank[a] > rank[b]) rank[a]++; if (rank[b] > rank[a]) swap(a, b); // Update the parent parent[b] = a; // Update the sum of set a setSum[a] += setSum[b]; } // Function to find the maximum element // from the sets after each operation void maxValues(vector<int> arr, vector<int> queries, int N) { // Stores the parent elements of // the sets vector<int> parent(N + 1); // Stores the rank of the sets vector<int> rank(N + 1, 0); // Stores the sum of the sets vector<int> setSum(N + 1, 0); // Stores the maximum element for // each query vector<int> currMax; for (int i = 1; i < N + 1; i++) { // Initially set is empty parent[i] = -1; // Update the sum as the // current element setSum[i] = arr[i - 1]; } // After the last query set will // be empty and sum will be 0 currMax.push_back(0); for (int i = N - 1; i > 0; i--) { // Check if the current element // is not in any set then make // parent as current element // of the queries if (parent[queries[i]] == -1) { parent[queries[i]] = queries[i]; } // Check left side of the queries[i] // is not added in any set if (queries[i] - 1 >= 0 && parent[queries[i] - 1] != -1) { // Add the queries[i] and the // queries[i]-1 in one set Union(parent, rank, setSum, queries[i], queries[i] - 1); } // Check right side of the queries[i] // is not added in any set if (queries[i] + 1 <= N && parent[queries[i] + 1] != -1) { // Add queries[i] and the // queries[i]+1 in one set Union(parent, rank, setSum, queries[i], queries[i] + 1); } // Update the maxAns maxAns = max(setSum[queries[i]], maxAns); // Push maxAns to the currMax currMax.push_back(maxAns); } // Print currMax values in the // reverse order for (int i = currMax.size() - 1; i >= 0; i--) { cout << currMax[i] << " "; } } // Driver Code int main() { vector<int> arr = { 1, 3, 2, 5 }; vector<int> queries = { 3, 4, 1, 2 }; int N = arr.size(); maxValues(arr, queries, N); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Stores the maximum integer of the sets // for each query static int maxAns = Integer.MIN_VALUE; // Function to perform the find operation // of disjoint set union static int Find(int [] parent, int a) { return parent[a] = (parent[a] == a) ? a : (Find( parent, parent[a])); } // Function to perform the Union operation // of disjoint set union static void Union(int [] parent, int [] rank, int [] setSum, int a, int b) { // Find the parent of a and b a = Find(parent, a); b = Find(parent, b); if (a == b) return; if (rank[a] > rank[b]) rank[a]++; if (rank[b] > rank[a]) { int x = a; a = b; b = x; } // Update the parent parent[b] = a; // Update the sum of set a setSum[a] += setSum[b]; } // Function to find the maximum element // from the sets after each operation static void maxValues(int [] arr, int [] queries, int N) { // Stores the parent elements of // the sets int [] parent = new int[N + 1]; // Stores the rank of the sets int [] rank = new int[N + 1]; // Stores the sum of the sets int [] setSum = new int[N + 1]; // Stores the maximum element for // each query Vector<Integer> currMax = new Vector<Integer>(); for (int i = 1; i < N + 1; i++) { // Initially set is empty parent[i] = -1; // Update the sum as the // current element setSum[i] = arr[i - 1]; } // After the last query set will // be empty and sum will be 0 currMax.add(0); for (int i = N - 1; i > 0; i--) { // Check if the current element // is not in any set then make // parent as current element // of the queries if (parent[queries[i]] == -1) { parent[queries[i]] = queries[i]; } // Check left side of the queries[i] // is not added in any set if (queries[i] - 1 >= 0 && parent[queries[i] - 1] != -1) { // Add the queries[i] and the // queries[i]-1 in one set Union(parent, rank, setSum, queries[i], queries[i] - 1); } // Check right side of the queries[i] // is not added in any set if (queries[i] + 1 <= N && parent[queries[i] + 1] != -1) { // Add queries[i] and the // queries[i]+1 in one set Union(parent, rank, setSum, queries[i], queries[i] + 1); } // Update the maxAns maxAns = Math.max(setSum[queries[i]], maxAns); // Push maxAns to the currMax currMax.add(maxAns); } // Print currMax values in the // reverse order for (int i = currMax.size() - 1; i >= 0; i--) { System.out.print(currMax.get(i)+ " "); } } // Driver Code public static void main(String[] args) { int [] arr = { 1, 3, 2, 5 }; int [] queries = { 3, 4, 1, 2 }; int N = arr.length; maxValues(arr, queries, N); } } // This code is contributed by shikhasingrajput
Python3
# Python 3 program for the above approach import sys # Stores the maximum integer of the sets # for each query maxAns = -sys.maxsize - 1 # Function to perform the find operation # of disjoint set union def Find(parent, a): if(parent[a] == a): return a return Find(parent, parent[a]) # Function to perform the Union operation # of disjoint set union def Union(parent, rank, setSum, a, b): # Find the parent of a and b a = Find(parent, a) b = Find(parent, b) if (a == b): return if (rank[a] > rank[b]): rank[a] += 1 if (rank[b] > rank[a]): swap(a, b) # Update the parent parent[b] = a # Update the sum of set a setSum[a] += setSum[b] # Function to find the maximum element # from the sets after each operation def maxValues(arr, queries, N): global maxAns # Stores the parent elements of # the sets parent = [0]*(N + 1) # Stores the rank of the sets rank = [0]*(N + 1) # Stores the sum of the sets setSum = [0]*(N + 1) # Stores the maximum element for # each query currMax = [] for i in range(1, N + 1): # Initially set is empty parent[i] = -1 # Update the sum as the # current element setSum[i] = arr[i - 1] # After the last query set will # be empty and sum will be 0 currMax.append(0) for i in range(N - 1, 0, -1): # Check if the current element # is not in any set then make # parent as current element # of the queries if (parent[queries[i]] == -1): parent[queries[i]] = queries[i] # Check left side of the queries[i] # is not added in any set if (queries[i] - 1 >= 0 and parent[queries[i] - 1] != -1): # Add the queries[i] and the # queries[i]-1 in one set Union(parent, rank, setSum, queries[i], queries[i] - 1) # Check right side of the queries[i] # is not added in any set if (queries[i] + 1 <= N and parent[queries[i] + 1] != -1): # Add queries[i] and the # queries[i]+1 in one set Union(parent, rank, setSum, queries[i], queries[i] + 1) # Update the maxAns maxAns = max(setSum[queries[i]], maxAns) # Push maxAns to the currMax currMax.append(maxAns) # Print currMax values in the # reverse order for i in range(len(currMax) - 1, -1, -1): print(currMax[i], end=" ") # Driver Code if __name__ == "__main__": arr = [1, 3, 2, 5] queries = [3, 4, 1, 2] N = len(arr) maxValues(arr, queries, N) # This code is contributed by ukasp.
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG{ // Stores the maximum integer of the sets // for each query static int maxAns = int.MinValue; // Function to perform the find operation // of disjoint set union static int Find(int [] parent, int a) { return parent[a] = (parent[a] == a) ? a : (Find( parent, parent[a])); } // Function to perform the Union operation // of disjoint set union static void Union(int [] parent, int [] rank, int [] setSum, int a, int b) { // Find the parent of a and b a = Find(parent, a); b = Find(parent, b); if (a == b) return; if (rank[a] > rank[b]) rank[a]++; if (rank[b] > rank[a]) { int x = a; a = b; b = x; } // Update the parent parent[b] = a; // Update the sum of set a setSum[a] += setSum[b]; } // Function to find the maximum element // from the sets after each operation static void maxValues(int [] arr, int [] queries, int N) { // Stores the parent elements of // the sets int [] parent = new int[N + 1]; // Stores the rank of the sets int [] rank = new int[N + 1]; // Stores the sum of the sets int [] setSum = new int[N + 1]; // Stores the maximum element for // each query List<int> currMax = new List<int>(); for (int i = 1; i < N + 1; i++) { // Initially set is empty parent[i] = -1; // Update the sum as the // current element setSum[i] = arr[i - 1]; } // After the last query set will // be empty and sum will be 0 currMax.Add(0); for (int i = N - 1; i > 0; i--) { // Check if the current element // is not in any set then make // parent as current element // of the queries if (parent[queries[i]] == -1) { parent[queries[i]] = queries[i]; } // Check left side of the queries[i] // is not added in any set if (queries[i] - 1 >= 0 && parent[queries[i] - 1] != -1) { // Add the queries[i] and the // queries[i]-1 in one set Union(parent, rank, setSum, queries[i], queries[i] - 1); } // Check right side of the queries[i] // is not added in any set if (queries[i] + 1 <= N && parent[queries[i] + 1] != -1) { // Add queries[i] and the // queries[i]+1 in one set Union(parent, rank, setSum, queries[i], queries[i] + 1); } // Update the maxAns maxAns = Math.Max(setSum[queries[i]], maxAns); // Push maxAns to the currMax currMax.Add(maxAns); } // Print currMax values in the // reverse order for (int i = currMax.Count - 1; i >= 0; i--) { Console.Write(currMax[i]+ " "); } } // Driver Code public static void Main(String[] args) { int [] arr = { 1, 3, 2, 5 }; int [] queries = { 3, 4, 1, 2 }; int N = arr.Length; maxValues(arr, queries, N); } } // This code is contributed by shikhasingrajput
Javascript
<script> // JavaScript program for the above approach // Stores the maximum integer of the sets // for each query let maxAns = -2147483648; // Function to perform the find operation // of disjoint set union const Find = (parent, a) => { return parent[a] = (parent[a] == a) ? a : (Find( parent, parent[a])); } // Function to perform the Union operation // of disjoint set union const Union = (parent, rank, setSum, a, b) => { // Find the parent of a and b a = Find(parent, a); b = Find(parent, b); if (a == b) return; if (rank[a] > rank[b]) rank[a]++; if (rank[b] > rank[a]) swap(a, b); // Update the parent parent[b] = a; // Update the sum of set a setSum[a] += setSum[b]; } // Function to find the maximum element // from the sets after each operation const maxValues = (arr, queries, N) => { // Stores the parent elements of // the sets let parent = new Array(N + 1).fill(0); // Stores the rank of the sets let rank = new Array(N + 1).fill(0); // Stores the sum of the sets let setSum = new Array(N + 1).fill(0); // Stores the maximum element for // each query let currMax = []; for (let i = 1; i < N + 1; i++) { // Initially set is empty parent[i] = -1; // Update the sum as the // current element setSum[i] = arr[i - 1]; } // After the last query set will // be empty and sum will be 0 currMax.push(0); for (let i = N - 1; i > 0; i--) { // Check if the current element // is not in any set then make // parent as current element // of the queries if (parent[queries[i]] == -1) { parent[queries[i]] = queries[i]; } // Check left side of the queries[i] // is not added in any set if (queries[i] - 1 >= 0 && parent[queries[i] - 1] != -1) { // Add the queries[i] and the // queries[i]-1 in one set Union(parent, rank, setSum, queries[i], queries[i] - 1); } // Check right side of the queries[i] // is not added in any set if (queries[i] + 1 <= N && parent[queries[i] + 1] != -1) { // Add queries[i] and the // queries[i]+1 in one set Union(parent, rank, setSum, queries[i], queries[i] + 1); } // Update the maxAns maxAns = Math.max(setSum[queries[i]], maxAns); // Push maxAns to the currMax currMax.push(maxAns); } // Print currMax values in the // reverse order for (let i = currMax.length - 1; i >= 0; i--) { document.write(`${currMax[i]} `); } } // Driver Code let arr = [1, 3, 2, 5]; let queries = [3, 4, 1, 2]; let N = arr.length; maxValues(arr, queries, N); // This code is contributed by rakeshsahni </script>
5 4 3 0
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA