Rearrange array elements excluded by given ranges to maximize sum of subarrays starting from the first index
Given an array arr[] consisting of N integers and an array Q[][], where each row denotes a range {l, r}(0 ? l ? r ? N – 1). The task is to find the maximum sum of all subarrays starting from index 0 by rearranging the array except the elements in the ranges given in Q[][].
Examples:
Input: arr[] = {-8, 4, -2, -6, 4, 7, 1}, Q[][] = {{0, 0}, {4, 5}}Output: -15
Explanation:
The given array can be rearranged as {-8, 4, 1, -2, 4, 7, -6}. Now, the sum of all the subarrays starting from the first index are:
Sum of arr[0, 0] = -8
Sum of arr[0, 1] = -8 + 4 = -4
Sum of arr[0, 2] = -8 + 4 + 1 = -3
Sum of arr[0, 3] = -8 + 4 + 1 + (-2) = -5
Sum of arr[0, 4] = -8 + 4 +1 + (-2) + 4 = -1
Sum of arr[0, 5] = -8 + 4 + 1 + (-2) + 4 + 7= 6
Sum of arr[0, 6] = -8 + 4 +1 + (-2) + 4 + 7 + (-6) = 0
The total sum = -8 + (-4) + (-3)+ (-5) + (-1) + 6 + 0 = -15Input: arr[] = {-8, 4, 3}, Q[][] = {{0, 2}}
Output: -13
Explanation: All elements are present in the given set of ranges. Therefore, no element can rearranged. Now, the sum of all subarrays from the first index are:
Sum of arr[0, 0] = -8
Sum of arr[0, 1] = -8 + 4 = -4
Sum of arr[0, 2] = -8 + 4 + 3 = -1
Total sum = -8 + (-4) + (-1) = -13
Approach: The idea is to first find the elements that cannot be rearranged. Then, sort the remaining elements in decreasing order and assign them to the indices such that the largest element will be assigned to the smallest index that is allowed to be rearranged. Follow the steps below to solve the problem:
- Create a vector s and v to store the indices and elements respectively, that can be rearranged.
- Traverse the elements for each range {l, r} and mark them visited.
- Traverse the given array and store the index i, if it is not marked visited.
- Sort the vector v in descending order.
- Insert the element in the given array as arr[s[i]] = v[i] where i is up to the number of elements that are allowed to be rearranged.
- After the above steps, print the sum of the prefix sums of the given array as the maximum sum.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that finds the maximum sum // all subarrays from the starting index // after rearranging the array int maxSum( int n, int a[], int l[][2], int q) { // Stores elements after rearranging vector< int > v; // Keeps track of visited elements int d[n] = { 0 }; // Traverse the queries for ( int i = 0; i < q; i++) { // Mark elements that are not // allowed to rearranged for ( int x = l[i][0]; x <= l[i][1]; x++) { if (d[x] == 0) { d[x] = 1; } } } // Stores the indices set< int > st; // Get indices and elements that // are allowed to rearranged for ( int i = 0; i < n; i++) { // Store the current index and // element if (d[i] == 0) { v.push_back(a[i]); st.insert(i); } } // Sort vector v in descending order sort(v.begin(), v.end(), greater< int >()); // Insert elements in array int c = 0; for ( auto it : st) { a[it] = v; c++; } // Stores the resultant sum int pref_sum = 0; // Stores the prefix sums int temp_sum = 0; // Traverse the given array for ( int i = 0; i < n; i++) { temp_sum += a[i]; pref_sum += temp_sum; } // Return the maximum sum return pref_sum; } // Driver Code int main() { // Given array int arr[] = { -8, 4, -2, -6, 4, 7, 1 }; // Given size int N = sizeof (arr) / sizeof (arr[0]); // Queries int q[][2] = { { 0, 0 }, { 4, 5 } }; // Number of queries int queries = sizeof (q) / sizeof (q[0]); // Function Call cout << maxSum(N, arr, q, queries); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function that finds the maximum sum // all subarrays from the starting index // after rearranging the array static int maxSum( int n, int a[], int [][]l, int q) { // Stores elements after rearranging Vector<Integer> v = new Vector<>(); // Keeps track of visited elements int []d = new int [n]; // Traverse the queries for ( int i = 0 ; i < q; i++) { // Mark elements that are not // allowed to rearranged for ( int x = l[i][ 0 ]; x <= l[i][ 1 ]; x++) { if (d[x] == 0 ) { d[x] = 1 ; } } } // Stores the indices HashSet<Integer> st = new HashSet<>(); // Get indices and elements that // are allowed to rearranged for ( int i = 0 ; i < n; i++) { // Store the current index and // element if (d[i] == 0 ) { v.add(a[i]); st.add(i); } } // Sort vector v in descending order Collections.sort(v); Collections.reverse(v); // Insert elements in array int c = 0 ; for ( int it : st) { a[it] = v.get(c); c++; } // Stores the resultant sum int pref_sum = 0 ; // Stores the prefix sums int temp_sum = 0 ; // Traverse the given array for ( int i = 0 ; i < n; i++) { temp_sum += a[i]; pref_sum += temp_sum; } // Return the maximum sum return pref_sum; } // Driver Code public static void main(String[] args) { // Given array int []arr = { - 8 , 4 , - 2 , - 6 , 4 , 7 , 1 }; // Given size int N = arr.length; // Queries int [][]q = { { 0 , 0 }, { 4 , 5 } }; // Number of queries int queries = q.length; // Function Call System.out.print(maxSum(N, arr, q, queries)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program for the # above approach # Function that finds the # maximum sum all subarrays # from the starting index # after rearranging the array def maxSum(n, a, l, q): # Stores elements after # rearranging v = [] # Keeps track of visited # elements d = [ 0 ] * n # Traverse the queries for i in range (q): # Mark elements that are not # allowed to rearranged for x in range (l[i][ 0 ], l[i][ 1 ] + 1 ): if (d[x] = = 0 ): d[x] = 1 # Stores the indices st = set ([]) # Get indices and elements # that are allowed to rearranged for i in range (n): # Store the current index and # element if (d[i] = = 0 ): v.append(a[i]) st.add(i) # Sort vector v in descending # order v.sort(reverse = True ) # Insert elements in array c = 0 for it in st: a[it] = v c + = 1 # Stores the resultant sum pref_sum = 0 # Stores the prefix sums temp_sum = 0 # Traverse the given array for i in range (n): temp_sum + = a[i] pref_sum + = temp_sum # Return the maximum sum return pref_sum # Driver Code if __name__ = = "__main__" : # Given array arr = [ - 8 , 4 , - 2 , - 6 , 4 , 7 , 1 ] # Given size N = len (arr) # Queries q = [[ 0 , 0 ], [ 4 , 5 ]] # Number of queries queries = len (q) # Function Call print (maxSum(N, arr, q, queries)) # This code is contributed by Chitranayal |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function that finds the maximum sum // all subarrays from the starting index // after rearranging the array static int maxSum( int n, int []a, int [,]l, int q) { // Stores elements after rearranging List< int > v = new List< int >(); // Keeps track of visited elements int []d = new int [n]; // Traverse the queries for ( int i = 0; i < q; i++) { // Mark elements that are not // allowed to rearranged for ( int x = l[i, 0]; x <= l[i, 1]; x++) { if (d[x] == 0) { d[x] = 1; } } } // Stores the indices HashSet< int > st = new HashSet< int >(); // Get indices and elements that // are allowed to rearranged for ( int i = 0; i < n; i++) { // Store the current index and // element if (d[i] == 0) { v.Add(a[i]); st.Add(i); } } // Sort vector v in descending order v.Sort(); v.Reverse(); // Insert elements in array int c = 0; foreach ( int it in st) { a[it] = v; c++; } // Stores the resultant sum int pref_sum = 0; // Stores the prefix sums int temp_sum = 0; // Traverse the given array for ( int i = 0; i < n; i++) { temp_sum += a[i]; pref_sum += temp_sum; } // Return the maximum sum return pref_sum; } // Driver Code public static void Main(String[] args) { // Given array int []arr = { -8, 4, -2, -6, 4, 7, 1 }; // Given size int N = arr.Length; // Queries int [,]q = { { 0, 0 }, { 4, 5 } }; // Number of queries int queries = q.GetLength(0); // Function Call Console.Write(maxSum(N, arr, q, queries)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach // Function that finds the maximum sum // all subarrays from the starting index // after rearranging the array function maxSum(n, a, l, q) { // Stores elements after rearranging let v = []; // Keeps track of visited elements let d = new Array(n); for (let i = 0; i < n; i++) { d[i] = 0; } // Traverse the queries for (let i = 0; i < q; i++) { // Mark elements that are not // allowed to rearranged for (let x = l[i][0]; x <= l[i][1]; x++) { if (d[x] == 0) { d[x] = 1; } } } // Stores the indices let st = new Set(); // Get indices and elements that // are allowed to rearranged for (let i = 0; i < n; i++) { // Store the current index and // element if (d[i] == 0) { v.push(a[i]); st.add(i); } } // Sort vector v in descending order v.sort( function (a, b){ return b - a;}); // Insert elements in array let c = 0; for (let it of st.values()) { a[it] = v; c++; } // Stores the resultant sum let pref_sum = 0; // Stores the prefix sums let temp_sum = 0; // Traverse the given array for (let i = 0; i < n; i++) { temp_sum += a[i]; pref_sum += temp_sum; } // Return the maximum sum return pref_sum; } // Driver Code // Given array let arr = [ -8, 4, -2, -6, 4, 7, 1 ]; // Given size let N = arr.length; // Queries let q = [ [ 0, 0 ], [ 4, 5 ] ]; // Number of queries let queries = q.length; // Function Call document.write(maxSum(N, arr, q, queries)); // This code is contributed by avanitrachhadiya2155 </script> |
-15
Time Complexity: O(N2)
Auxiliary Space: O(N)
Contact Us