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>
Producción:
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