Maximum sum of segments among all segments formed in array after Q queries

2024-03-31 23:29| 来源: 网络整理| 查看: 265

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 0Explanation: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 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 arr, vector queries, int N) { // Stores the parent elements of // the sets vector parent(N + 1); // Stores the rank of the sets vector rank(N + 1, 0); // Stores the sum of the sets vector setSum(N + 1, 0); // Stores the maximum element for // each query vector 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 = 0; i--) { cout 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 currMax = new Vector(); 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 = 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 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 currMax = new List(); 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 = 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

// 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 = 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 Output: 5 4 3 0

Time Complexity: O(N*log N)Auxiliary Space: O(N)

Last Updated : 29 Sep, 2021 Like Article Save Article Previous Number of minimum length paths between 1 to N including each node Next Count of non-decreasing numeric string formed by replacing wild card '?' Share your thoughts in the comments Please Login to comment...

【本文地址】

公司简介

联系我们