Maximize Array sum by adding multiple of another Array element in given ranges
Given two arrays X[] and Y[] of length N along with Q queries each of type [L, R] that denotes the subarray of X[] from L to R. The task is to find the maximum sum that can be obtained by applying the following operation for each query:
- Choose an element from Y[].
- Add multiples with alternate +ve and -ve signs to the elements of the subarray. i.e., if the chosen element is 4, then modify the subarray as {XL+ 4, XL+1 – 8, . . . (till Rth) index}
- Delete the element chosen from Y.
Note: 1-based indexing is used here.
Examples:
Input: N = 4, X[] = {1, 2, 3, 4}, Y[] = {2, 3, 5, 6}, K = 1, query = {{3, 3}}
Output: 16
Explanation:
Number of queries = 1
Sub-array from start to end index of X[]: {3}
Chose 6 from Y[] and then add alternative series of multiple of 6 = {3 + 6} = {9}. Rest of the elements except the sub-array will remain the same, Therefore, new X[] is: {1, 2, 9, 4}. The maximum sum that can obtain from
X[] = 1+ 2+ 9+ 4 = 16Input: N = 5, X[] = {5, 7, 2, 1, 8}, Y[] = {1, 2, 3, 4, 5}, K = 2, queries = {{1, 4}, {1, 5}}
Output: 36
Explanation:
start = 1, end = 4
The subarray = {7, 2, 1, 8}
Lets chose 1 from Y[] and add series of multiple of 1 in subarray = {7 + 1, 2 – 2, 1 + 3, 8 – 4} = {8, 0, 4, 4}.
X[]: {5, 8, 0, 4, 4}
Now, start = 1, end = 5
The subarray = {5, 8, 0, 4, 4}
lets chose 5 from Y[] and add series of multiple of 5 in subarray = {5 + 5, 8 – 10, 0 + 15, 4 – 20, 4 + 25} = {10, -2, 15, -16, 29}. Now updated X[] will be: {10, -2, 15, -16, 29}.
Overall sum of X[] is : (10 – 2 + 15 – 16 + 29) = 36. It can be verified that this sum is maximum possible.
Intuition: The intuition behind the approach is provided below
Let us take an example of series of multiple of an integer let say K. Then the series will be as the picture below:
It can be seen clearly that if subarray of series is of odd length then it will contribute a positive sum in the overall sum, While series of even length will contribute negative sum to the total sum.
So the optimal idea is to add the multiples of the biggest value to the largest odd length subarray and the multiples of the smallest value to the largest even length subarray.
Naive Approach:
In this method, we will do the same as mentioned in the problem statement. We will traverse on each sub-array by the given start and end indices in each query and add series of multiple of the optimal element at that current state so that our sum is maximized.
Follow the steps mentioned below to implement the idea:
- Make ArrayList of Pairs<Start, End> DataType and initialize it with Pairs of start and end indices of given sub-arrays in query.
- Sort Queries in ArrayList according to the length of sub-arrays, Formally arrange Pairs in descending order of length.
- Sort Y[]. It will be convenient to get minimum and maximum elements and delete them after use.
- Run a loop number of times queries are asked then do the following steps:
- Calculate the length of the current subarray. If the length is even take a minimum element of Y[] else take the maximum.
- Traverse on sub-array and add the series of Multiple into it.
- Delete the used element of Y[].
- Calculate the overall sum of elements present in the X[] by traversing array X[]
- Print the sum as the required answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include<bits/stdc++.h> using namespace std; // Function to get maximum value after K // queries void maximumSum(int X[], int Y[], int N, int K,vector<int> &list) { // Variable for holding maximum sum that can be // obtained long sum = 0; // Loop for calculating initial sum of X[] for (int i = 0; i < N; i++) { sum += X[i]; } // Start pointer for Y[] int s = 0; // End pointer of Y[] int e = N - 1; // Loop for Executing Queries in descending order of // length for (int i = list.size() - 1; i >= 0; i--) { // Variable to hold length of subarray int length = list[i]; // element needed to be add optimally int element = length % 2 == 0 ? Y[s] : Y[e]; // Increasing or decreasing start and end // pointers After using element at that pointers if (length % 2 == 0) { s++; } else { e--; } // Condition when length is even if (length % 2 == 0) { // Subtracting from the // overall sum sum = sum - ((length / 2) * element); } else { // Adding increment in // overall sum sum = sum + (((length + 1) / 2) * element); } } // Printing value of sum cout<<sum; } // Driver code int main() { int N = 3; int X[] = { 1, 2, 3 }; int Y[] = { 4, 3, 1 }; int K = 2; // Start[] and end[] of K length holds // starting and ending indices // of sub-array int start[] = { 1, 1 }; int end[] = { 1, 3 }; // ArrayList of length of sub-arrays in each query vector<int> list; for (int i = 0; i < K; i++) { list.push_back((end[i] - start[i]) + 1); } // Sorting ArrayList sort(list.begin(),list.end()); // Sorting Y[] using in-built sort function sort(Y,Y+N); // Function call for getting maximum Sum maximumSum(X, Y, N, K, list); return 0; } // This code is contributed by Pushpesh Raj.
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; // User defined Pair class class Pair { // Two variables to store start and end indices // respectively int x, y; // Constructor of Pair class Pair(int x, int y) { this.x = x; this.y = y; } // Function for returning length of a Pair(Formally // length of sub-array) According to 1 based indexing int length() { return (this.y - this.x) + 1; } } class GFG { // Function to get maximum Sum after // K queries static void maximumSum(int X[], int Y[], int N, ArrayList<Pair> list, int K) { // Variable to calculate overall sum long sum = 0; // Maintaining two pointers to get // maximum and minimum element from // Y[] int s = 0; int e = Y.length - 1; // Loop for Traversing on Pairs for (int i = 0; i < list.size(); i++) { // Variable S holds start index // of query int S = list.get(i).x; // Variable E holds start index // of query int E = list.get(i).y; // length variable stores length // of sub-array using S and // E(1 based indexing) int length = list.get(i).length(); // If length is even the minimum // element will be store in // "element" variable else Maximum // element will be store in it int element = length % 2 == 0 ? Y[s] : Y[e]; // Removing chose element from // Y[] if (length % 2 == 0) { s++; } else { e--; } // Counter initialized to 1 int counter = 1; // Loop for traversing on given // sub-array as queries // 1 based indexing, Therefore, S-1 to <E for (int j = S - 1; j < E; j++) { // The below if-else // conditions is adding AP // of +ve and -ve elements if (counter % 2 != 0) { X[j] = X[j] + (counter * element); } else { X[j] = X[j] - (counter * element); } // Incrementing counter counter++; } } // Loop for traversing on X[] after // K Queries so that we can obtain // its sum for (int i = 0; i < N; i++) { // Adding element of X[] into // sum variable sum += X[i]; } // Printing value of sum System.out.println(sum); } // Driver code public static void main(String[] args) { int N = 3; int[] X = { 1, 2, 3 }; int[] Y = { 1, 3, 4 }; int K = 2; // Start[] and end[] of K length // holds starting and ending indices // of sub-array int[] start = { 1, 1 }; int[] end = { 3, 1 }; // ArrayList of Pair type to store given start and // end indices as Pair<start, end> ArrayList<Pair> list = new ArrayList<>(); // Loop for initializing list as Pairs for (int i = 0; i < K; i++) { list.add(new Pair(start[i], end[i])); } // Sorting list in descending order using user // defined Selection-sort function SortList(list); // sorting Y[] using in-built sort function Arrays.sort(Y); // function call for obtaining maximum sum maximumSum(X, Y, N, list, K); } // User defined Function for sorting list(Selection Sort // is used) static void SortList(ArrayList<Pair> list) { for (int i = 0; i < list.size() - 1; i++) { int max = i; for (int j = i + 1; j < list.size(); j++) { if (list.get(max).length() < list.get(j).length()) { max = j; } } Pair temp = new Pair(list.get(i).x, list.get(i).y); list.get(i).x = list.get(max).x; list.get(i).y = list.get(max).y; list.get(max).x = temp.x; list.get(max).y = temp.y; } } }
Python3
# Python implementation from typing import List def maximumSum(X: List[int], Y: List[int], N: int, K: int, list: List[int]) -> None: # Variable for holding maximum sum that can be obtained sum = 0 # Loop for calculating initial sum of X[] for i in range(N): sum += X[i] # Start pointer for Y[] s = 0 # End pointer of Y[] e = N - 1 # Loop for Executing Queries in descending order of length for i in range(len(list) - 1, -1, -1): # Variable to hold length of subarray length = list[i] # element needed to be add optimally element = Y[s] if length % 2 == 0 else Y[e] # Increasing or decreasing start and end pointers After using element at that pointers if length % 2 == 0: s += 1 else: e -= 1 # Condition when length is even if length % 2 == 0: # Subtracting from the overall sum sum = sum - ((length // 2) * element) else: # Adding increment in overall sum sum = sum + (((length + 1) // 2) * element) # Printing value of sum print(sum) # Driver code def main(): N = 3 X = [1, 2, 3] Y = [4, 3, 1] K = 2 # Start[] and end[] of K length holds starting and ending indices of sub-array start = [1, 1] end = [1, 3] # ArrayList of length of sub-arrays in each query arr_list = [(end[i] - start[i]) + 1 for i in range(K)] # Sorting ArrayList arr_list.sort() # Sorting Y[] using in-built sort function Y.sort() # Function call for getting maximum Sum maximumSum(X, Y, N, K, arr_list) if __name__ == '__main__': main() # This code is contributed by ksam24000
Javascript
// JavaScript code to implement the approach // Function to get maximum value after K // queries function maximumSum(X, Y, N, K, list) { // Variable for holding maximum sum that can be // obtained sum = 0; // Loop for calculating initial sum of X[] for (let i = 0; i < N; i++) { sum += X[i]; } // Start pointer for Y[] let s = 0; // End pointer of Y[] let e = N - 1; // Loop for Executing Queries in descending order of // length for (let i = list.length - 1; i >= 0; i--) { // Variable to hold length of subarray let length = list[i]; // element needed to be add optimally let element = length % 2 == 0 ? Y[s] : Y[e]; // Increasing or decreasing start and end // poleters After using element at that poleters if (length % 2 == 0) { s++; } else { e--; } // Condition when length is even if (length % 2 == 0) { // Subtracting from the // overall sum sum = sum - ((length / 2) * element); } else { // Adding increment in // overall sum sum = sum + (((length + 1) / 2) * element); } } // Printing value of sum document.write(sum); } // Driver code let N = 3; let X = [ 1, 2, 3 ]; let Y = [4, 3, 1 ]; let K = 2; // Start[] and end[] of K length holds // starting and ending indices // of sub-array let start = [1, 1 ]; let end = [1, 3 ]; // ArrayList of length of sub-arrays in each query let list=[]; for (let i = 0; i < K; i++) { list.push((end[i] - start[i]) + 1); } // Sorting ArrayList list.sort(); // Sorting Y[] using in-built sort function Y.sort(); // Function call for getting maximum Sum maximumSum(X, Y, N, K, list); // This code is contributed by poojaagarwal2.
C#
// C# implementation of the above approach using System; using System.Collections.Generic; class GFG { // Function to get maximum value after K // queries static void maximumSum(int[] X, int[] Y, int N, int K,List<int> list) { // Variable for holding maximum sum that can be // obtained long sum = 0; // Loop for calculating initial sum of X[] for (int i = 0; i < N; i++) { sum += X[i]; } // Start pointer for Y[] int s = 0; // End pointer of Y[] int e = N - 1; // Loop for Executing Queries in descending order of // length for (int i = list.Count - 1; i >= 0; i--) { // Variable to hold length of subarray int length = list[i]; // element needed to be add optimally int element = length % 2 == 0 ? Y[s] : Y[e]; // Increasing or decreasing start and end // pointers After using element at that pointers if (length % 2 == 0) { s++; } else { e--; } // Condition when length is even if (length % 2 == 0) { // Subtracting from the // overall sum sum = sum - ((length / 2) * element); } else { // Adding increment in // overall sum sum = sum + (((length + 1) / 2) * element); } } // Printing value of sum Console.Write(sum); } static public void Main() { // Driver code int N = 3; int[] X = { 1, 2, 3 }; int[] Y = { 4, 3, 1 }; int K = 2; // Start[] and end[] of K length holds // starting and ending indices // of sub-array int[] start = { 1, 1 }; int[] end = { 1, 3 }; // ArrayList of length of sub-arrays in each query List<int> list=new List<int>(); for (int i = 0; i < K; i++) { list.Add((end[i] - start[i]) + 1); } // Sorting ArrayList list.Sort(); // Sorting Y[] using in-built sort function Array.Sort(Y); // Function call for getting maximum Sum maximumSum(X, Y, N, K, list); } } // This code is contributed by ratiagrawal.
17
Time Complexity: O(N2), As Selection Sort is used
Auxiliary Space: O(K), As ArrayList of Pair is used of Size K
Efficient Approach:
In this method, we will not be traversing on sub-array for each query. We will direct obtain the increment or decrement using a direct mathematical formula. From the intuition we can conclude that:
- If length of sub-array is odd, Then increment in overall sum of X[] will be = (((length + 1) / 2) * element)
- If the length of the sub-array is even, Then the decrement in overall sum of X[] will be = – ((length / 2) * element)
Here element is chosen element from Y[], and length is length of sub-array in query.
Follow the steps mentioned below to implement the idea:
- Create a variable sum and calculate the overall sum of the elements initially present in X[].
- Create a list and initialize it with the length of subarrays in K queries.
- Sort list and the array Y[].
- Run a loop from the back to the front of the list(Formally Descending order length) and do the following:
- If length is odd add (((length+1)/2)*element) in sum variable else subtract ((length/2)*element) from sum variable.
- Print the value of the sum variable.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include<bits/stdc++.h> using namespace std; // Function to get maximum value after K // queries void maximumSum(int X[], int Y[], int N, int K,vector<int> &list) { // Variable for holding maximum sum that can be // obtained long sum = 0; // Loop for calculating initial sum of X[] for (int i = 0; i < N; i++) { sum += X[i]; } // Start pointer for Y[] int s = 0; // End pointer of Y[] int e = N - 1; // Loop for Executing Queries in descending order of // length for (int i = list.size() - 1; i >= 0; i--) { // Variable to hold length of subarray int length = list[i]; // element needed to be add optimally int element = length % 2 == 0 ? Y[s] : Y[e]; // Increasing or decreasing start and end // pointers After using element at that pointers if (length % 2 == 0) { s++; } else { e--; } // Condition when length is even if (length % 2 == 0) { // Subtracting from the // overall sum sum = sum - ((length / 2) * element); } else { // Adding increment in // overall sum sum = sum + (((length + 1) / 2) * element); } } // Printing value of sum cout<<sum; } // Driver code int main() { int N = 3; int X[] = { 1, 2, 3 }; int Y[] = { 4, 3, 1 }; int K = 2; // Start[] and end[] of K length holds // starting and ending indices // of sub-array int start[] = { 1, 1 }; int end[] = { 1, 3 }; // ArrayList of length of sub-arrays in each query vector<int> list; for (int i = 0; i < K; i++) { list.push_back((end[i] - start[i]) + 1); } // Sorting ArrayList sort(list.begin(),list.end()); // Sorting Y[] using in-built sort function sort(Y,Y+N); // Function call for getting maximum Sum maximumSum(X, Y, N, K, list); return 0; } // This code is contributed by sanjoy_62.
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to get maximum value after K // queries static void maximumSum(int X[], int Y[], int N, int K, ArrayList<Integer> list) { // Variable for holding maximum sum that can be // obtained long sum = 0; // Loop for calculating initial sum of X[] for (int i = 0; i < X.length; i++) { sum += X[i]; } // Start pointer for Y[] int s = 0; // End pointer of Y[] int e = Y.length - 1; // Loop for Executing Queries in descending order of // length for (int i = list.size() - 1; i >= 0; i--) { // Variable to hold length of subarray int length = list.get(i); // element needed to be add optimally int element = length % 2 == 0 ? Y[s] : Y[e]; // Increasing or decreasing start and end // pointers After using element at that pointers if (length % 2 == 0) { s++; } else { e--; } // Condition when length is even if (length % 2 == 0) { // Subtracting from the // overall sum sum = sum - ((length / 2) * element); } else { // Adding increment in // overall sum sum = sum + (((length + 1) / 2) * element); } } // Printing value of sum System.out.println(sum); } // Driver code public static void main(String[] args) { int N = 3; int[] X = { 1, 2, 3 }; int[] Y = { 4, 3, 1 }; int K = 2; // Start[] and end[] of K length holds // starting and ending indices // of sub-array int[] start = { 1, 1 }; int[] end = { 1, 3 }; // ArrayList of length of sub-arrays in each query ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < K; i++) { list.add((end[i] - start[i]) + 1); } // Sorting ArrayList list.sort(null); // Sorting Y[] using in-built sort function Arrays.sort(Y); // Function call for getting maximum Sum maximumSum(X, Y, N, K, list); } }
Python3
# Function to get maximum value after K # queries def maximumSum(X, Y, N, K, list): # Variable for holding maximum sum that can be # obtained sum = 0 # Loop for calculating initial sum of X[] for i in range(N): sum += X[i] # Start pointer for Y[] s = 0 # End pointer of Y[] e = N-1 # Loop for Executing Queries in descending order of # length for i in reversed(range(len(list))): # Variable to hold length of subarray length = list[i] # element needed to be add optimally element = Y[s] if length % 2 == 0 else Y[e] # Increasing or decreasing start and end # pointers After using element at that pointers if length%2 == 0: s += 1 else: e -= 1 # Condition when length is even if length%2 == 0: # Subtracting from the # overall sum sum = sum - ((length/2) * element) else: # Adding increment in # overall sum sum = sum + (((length + 1) // 2) * element) # Printing value of sum print(sum) # Driver code if __name__ == "__main__": N = 3 X = [1, 2, 3] Y = [4, 3, 1] K = 2 # Start[] and end[] of K length holds # starting and ending indices # of sub-array start = [1, 1] end = [1, 3] # ArrayList of length of sub-arrays in each query list = [] for i in range(0, K): list.append((end[i] - start[i]) + 1) # Sorting ArrayList list.sort() # Sorting Y[] using in-built sort function Y.sort() # Function call for getting maximum Sum maximumSum(X, Y, N, K, list) # This code is contributed by sanjoy_62.
C#
// C# code to implement the approach using System; using System.Collections; using System.Collections.Generic; public class GFG { // Function to get maximum value after K // queries static void maximumSum(int[] X, int[] Y, int N, int K, ArrayList list) { // Variable for holding maximum sum that can be // obtained long sum = 0; // Loop for calculating initial sum of X[] for (int i = 0; i < X.Length; i++) { sum += X[i]; } // Start pointer for Y[] int s = 0; // End pointer of Y[] int e = Y.Length - 1; // Loop for Executing Queries in descending order of // length for (int i = list.Count - 1; i >= 0; i--) { // Variable to hold length of subarray int length = (int)list[i]; // element needed to be add optimally int element = length % 2 == 0 ? Y[s] : Y[e]; // Increasing or decreasing start and end // pointers After using element at that pointers if (length % 2 == 0) { s++; } else { e--; } // Condition when length is even if (length % 2 == 0) { // Subtracting from the // overall sum sum = sum - ((length / 2) * element); } else { // Adding increment in // overall sum sum = sum + (((length + 1) / 2) * element); } } // Printing value of sum Console.WriteLine(sum); } static public void Main() { // Code int N = 3; int[] X = { 1, 2, 3 }; int[] Y = { 4, 3, 1 }; int K = 2; // Start[] and end[] of K length holds // starting and ending indices // of sub-array int[] start = { 1, 1 }; int[] end = { 1, 3 }; // ArrayList of length of sub-arrays in each query ArrayList list = new ArrayList(); for (int i = 0; i < K; i++) { list.Add((end[i] - start[i]) + 1); } // Sorting ArrayList list.Sort(); // Sorting Y[] using in-built sort function Array.Sort(Y); // Function call for getting maximum Sum maximumSum(X, Y, N, K, list); } } // This code is contributed by lokesh
Javascript
// Javascript code to implement the approach // Function to get maximum value after K // queries function maximumSum(X, Y, N, K, list) { // Variable for holding maximum sum that can be // obtained let sum = 0; // Loop for calculating initial sum of X[] for (let i = 0; i < N; i++) { sum += X[i]; } // Start pointer for Y[] let s = 0; // End pointer of Y[] let e = N - 1; // Loop for Executing Queries in descending order of // length for (let i = list.length - 1; i >= 0; i--) { // Variable to hold length of subarray let length = list[i]; // element needed to be add optimally let element = length % 2 == 0 ? Y[s] : Y[e]; // Increasing or decreasing start and end // pointers After using element at that pointers if (length % 2 == 0) { s++; } else { e--; } // Condition when length is even if (length % 2 == 0) { // Subtracting from the // overall sum sum = sum - ((length / 2) * element); } else { // Adding increment in // overall sum sum = sum + (((length + 1) / 2) * element); } } // Printing value of sum console.log(sum); } // Driver code let N = 3; let X = [ 1, 2, 3 ]; let Y = [ 4, 3, 1 ]; let K = 2; // Start[] and end[] of K length holds // starting and ending indices // of sub-array let start = [ 1, 1 ]; let end = [ 1, 3 ]; // ArrayList of length of sub-arrays in each query let list=new Array(); for (let i = 0; i < K; i++) { list.push((end[i] - start[i]) + 1); } // Sorting ArrayList list.sort(); // Sorting Y[] using in-built sort function Y.sort(); // Function call for getting maximum Sum maximumSum(X, Y, N, K, list);
17
Time Complexity: O(Y * log Y), As sorting is performed on Y[].
Auxiliary Space: O(K), As an ArrayList of size K is used.
Related Articles:
Contact Us