Given two arrays arr[](1-based indexing) and queries[] consisting of N integers and queries[] contains a permutation of the first N natural numbers, the task is to perform the query on the array and find the maximum sum of segments among all segments formed such that in each query queries[i] the array element at index queries[i] is deleted and that segment is divided into 2 segments.
Examples:
Input: arr[] = {1, 3, 2, 5}, queries[] = {3, 4, 1, 2}
Output: 5 4 3 0
Explanation:
Following are the queries performed:
- Query 1: Remove the element at index 3 break the current array into {1, 3}, {5}. The maximum sum among all segments is 5.
- Query 2: Remove the element at index 4 break the current array into {1, 3} {}. The maximum sum among all segments is 4.
- Query 3: Remove the element at index 1 break the current array into {1}, {}. The maximum sum among all segments is 1.
- Query 4: Remove the element at index 2 break the current array into {}, {}. The maximum sum among all segments is 0.
Input: arr[] = {1, 2, 3, 4, 5}, queries[] = {4, 2, 3, 5, 1}
Output: 6 5 5 1 0
Approach: The given problem can be solved by using Disjoint Set Union Data Structure. The idea is to store all the queries in an array, initially, all the elements are in different sets, process the queries in reverse order, for each query make union operation for the current element with its left and right side elements using the find operation, parallelly keep track of the maximum element then store it in an array, then print the array elements in the reverse order. Follow the steps below to solve the problem:
- Initialize the vectors parent(N + 1), rank(N + 1, 0), setSum(N + 1, 0) and currMax.
- Iterate over the range [1, N+1) using the variable i and set the value of parent[i] as -1 and setSum[i] as arr[i – 1].
- Push the value 0 into the vector currMax[] because after the last query the answer will be 0.
- Iterate over the range [N – 1, 0] in the reverse order using the variable i and perform the following steps:
- If parent[queries[I]] is -1, then set it as queries[i].
- If queries[i] – 1 >= 0 && parent[queries[i] – 1] != -1, then call for function operation union(parent, rank, setSum, queries[I], queries[I]-1).
- If queries[i] + 1 <= N && parent[queries[i] + 1] != -1, then call for function operation union(parent, rank, setSum, queries[I], queries[I]+1).
- Set the value of maxAns as the maximum of maxAns or setSum[queries[I]] and push the value of maxAns into the vector currMax[].
- Reverse the vector currMax[] and print it’s values as the answer.
Below is the implementation of the above algorithm:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Stores the maximum integer of the sets// for each queryint maxAns = INT_MIN;// Function to perform the find operation// of disjoint set unionint 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 unionvoid 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 operationvoid 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 Codeint 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 approachimport java.util.*;class GFG{// Stores the maximum integer of the sets// for each querystatic int maxAns = Integer.MIN_VALUE;// Function to perform the find operation// of disjoint set unionstatic 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 unionstatic 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 operationstatic 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 Codepublic 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 approachimport sys# Stores the maximum integer of the sets# for each querymaxAns = -sys.maxsize - 1# Function to perform the find operation# of disjoint set uniondef Find(parent, a): if(parent[a] == a): return a return Find(parent, parent[a])# Function to perform the Union operation# of disjoint set uniondef 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 operationdef 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 Codeif __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 approachusing System;using System.Collections.Generic;public class GFG{// Stores the maximum integer of the sets// for each querystatic int maxAns = int.MinValue;// Function to perform the find operation// of disjoint set unionstatic 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 unionstatic 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 operationstatic 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 Codepublic 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> |
Output:
5 4 3 0
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
