Maximize sum of array elements removed by performing the given operations
Given two arrays arr[] and min[] consisting of N integers and an integer K. For each index i, arr[i] can be reduced to at most min[i]. Consider a variable, say S(initially 0). The task is to find the maximum value of S that can be obtained by performing the following operations:
- Choose an index i and add max(arr[i], min[i]) to S.
- Remove the chosen element from arr[] and its corresponding minimum value.
- Decrease each remaining value by K if it is greater than its corresponding minimum value in min[].
Examples:
Input: arr[] = {2, 4, 5, 8}, min[] = {1, 4, 5, 5}, K = 3
Output: 18
Explanation:
Choose the elements in the following order:
Step 1: Choose element 8. Now, S = 8 and arr[] = {-1, 4, 5} and min[] = {1, 4, 5}
Step 2: Choose element 5. Now, S = 8 + 5 = 13 and arr[] = {-1, 4} and min[] = {1, 4}
Step 3: Choose element 5. Now, S = 8 + 5 + 4 = 17 and arr[] = {-1} and min[] = {1}
Step 4: Choose element -1, but -1 < min[0]. Therefore, choose 1.
Hence, S = 8 + 5 + 4 + 1 = 18.Input: arr[] = {3, 5, 2, 1}, min[] = {3, 2, 1, 3}, K = 2
Output: 12
Explanation:
Choose the elements in the following order:
Step 1: Choose element 5. Now, S = 5 and arr[] = {3, 0, 1} and min[] = {3, 1, 3}
Step 2: Choose element 3. Now, S = 5 + 3 = 8 and arr[] = {0, 1} and min[] = {1, 3}
Step 3: Choose element 3 from min[]. Now, S = 5 + 3 + 3 = 11 and arr[] = {0} and min[] = {1}
Step 4: Choose element 1 from min[].
Hence, S = 5 + 3 + 3 + 1 = 12.
Naive Approach: The simplest approach is to traverse the given array and perform the given operations in the array itself. Follow the steps below to solve the problem:
- Traverse the array and find the maximum array element.
- Add the maximum value in S and remove the maximum.
- Decrease the remaining element by K if they satisfy the above conditions.
- Repeat the above steps until the given array becomes empty.
- After traversing, print S.
Time Complexity: O(N2), where N is the length of the given array.
Auxiliary Space: O(N)
Efficient Approach: The idea is to sort the given array in decreasing order. Then, print the maximum value of S by choosing the elements greedily. Follow the steps below to solve the problem:
- Pair the elements of the array arr[] with their corresponding values in min[].
- Sort the array of pairs in decreasing order according to array arr[].
- Initially, choose the maximum element and increase K by its initial value.
- Now, choose the next maximum element by decreasing its value by the current K.
- Repeat the above steps, until all the array elements are traversed and print the value of S.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum sum of // the array arr[] where each element // can be reduced to at most min[i] void findMaxSum(vector< int > arr, int n, vector< int > min, int k, int & S) { // Stores the pair of arr[i] & min[i] vector<pair< int , int > > A; for ( int i = 0; i < n; i++) { A.push_back({ arr[i], min[i] }); } // Sorting vector of pairs sort(A.begin(), A.end(), greater<pair< int , int > >()); int K = 0; // Traverse the vector of pairs for ( int i = 0; i < n; i++) { // Add to the value of S S += max(A[i].first - K, A[i].second); // Update K K += k; } } // Driver Code int main() { vector< int > arr, min; // Given array arr[], min[] arr = { 3, 5, 2, 1 }; min = { 3, 2, 1, 3 }; int N = arr.size(); // Given K int K = 3; int S = 0; // Function Call findMaxSum(arr, N, min, K, S); // Print the value of S cout << S; return 0; } |
Java
// Java program for the // above approach import java.util.*; class GFG{ static int S; // Function to find the maximum sum of // the array arr[] where each element // can be reduced to at most min[i] static void findMaxSum( int [] arr, int n, int [] min, int k) { // Stores the pair of arr[i] & min[i] ArrayList< int []> A = new ArrayList<>(); for ( int i = 0 ; i < n; i++) { A.add( new int []{arr[i], min[i]}); } // Sorting vector of pairs Collections.sort(A, (a, b) -> b[ 0 ] - a[ 0 ]); int K = 0 ; // Traverse the vector of pairs for ( int i = 0 ; i < n; i++) { // Add to the value of S S += Math.max(A.get(i)[ 0 ] - K, A.get(i)[ 1 ]); // Update K K += k; } } // Driver code public static void main (String[] args) { // Given array arr[], min[] int [] arr = { 3 , 5 , 2 , 1 }; int [] min = { 3 , 2 , 1 , 3 }; int N = arr.length; // Given K int K = 3 ; S = 0 ; // Function Call findMaxSum(arr, N, min, K); // Print the value of S System.out.println(S); } } // This code is contributed by offbeat |
Python3
# Python3 program for the above approach # Function to find the maximum sum of # the array arr[] where each element # can be reduced to at most min[i] def findMaxSum(arr, n, min , k, S): # Stores the pair of arr[i] & min[i] A = [] for i in range (n): A.append((arr[i], min [i])) # Sorting vector of pairs A = sorted (A) A = A[:: - 1 ] K = 0 # Traverse the vector of pairs for i in range (n): # Add to the value of S S + = max (A[i][ 0 ] - K, A[i][ 1 ]) # Update K K + = k return S # Driver Code if __name__ = = '__main__' : arr, min = [], [] # Given array arr[], min[] arr = [ 3 , 5 , 2 , 1 ] min = [ 3 , 2 , 1 , 3 ] N = len (arr) # Given K K = 3 S = 0 # Function Call S = findMaxSum(arr, N, min , K, S) # Print the value of S print (S) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; using System.Collections.Generic; using System.Linq; class GFG{ static int S; // Function to find the maximum sum of // the array arr[] where each element // can be reduced to at most min[i] static void findMaxSum( int [] arr, int n, int [] min, int k) { // Stores the pair of arr[i] & min[i] List<List< int >> A = new List<List< int >>(); for ( int i = 0; i < n; i++) { A.Add( new List< int >()); A[i].Add(arr[i]); A[i].Add(min[i]); } // Sorting vector of pairs A = A.OrderBy(lst => lst[0]).ToList(); A.Reverse(); int K = 0; // Traverse the vector of pairs for ( int i = 0; i < n; i++) { // Add to the value of S S += Math.Max(A[i][0] - K, A[i][1]); // Update K K += k; } } // Driver code static public void Main() { // Given array arr[], min[] int [] arr = { 3, 5, 2, 1 }; int [] min = { 3, 2, 1, 3 }; int N = arr.Length; // Given K int K = 3; S = 0; // Function Call findMaxSum(arr, N, min, K); // Print the value of S Console.WriteLine(S); } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // Javascript program for the above approach var S =0; // Function to find the maximum sum of // the array arr[] where each element // can be reduced to at most min[i] function findMaxSum(arr, n, min, k) { // Stores the pair of arr[i] & min[i] var A = []; for ( var i = 0; i < n; i++) { A.push([arr[i], min[i] ]); } // Sorting vector of pairs A.sort((a,b)=> b[0]-a[0]); var K = 0; // Traverse the vector of pairs for ( var i = 0; i < n; i++) { // Add to the value of S S += Math.max(A[i][0] - K, A[i][1]); // Update K K += k; } } // Driver Code var arr = [], min = []; // Given array arr[], min[] arr = [3, 5, 2, 1]; min = [3, 2, 1, 3]; var N = arr.length; // Given K var K = 3; // Function Call findMaxSum(arr, N, min, K, S); // Print the value of S document.write( S); </script> |
12
Time Complexity: O(N*log N), where N is the length of the given array.
Auxiliary Space: O(N)