Maximum possible array sum after performing the given operation

In this question, we will perform the given operation on the array elements and find the final maximum sum.

Here, in each operation, we can select at most X[p] elements from the array and replace them with Y[p] elements to maximize the sum.

In the simple approach, we will find X[p] array elements that are smaller than Y[p] elements and replace them with Y[p].

In an efficient approach, we will use a priority queue to get the maximum sum.

Problem Statement− We are given a nums[] array containing N numbers. At the same time, we are given X[] and Y[] arrays containing M integers. We need to perform the following operations on the nums[] array.

• We need to perform M operations on each element of the X[] and Y[] elements. In each operation, we need to select the largest X[p] element from the array nums[] and replace it with Y[p].

The given task is to find the maximum sum of the elements of the nums[] array after performing M operations.

ExampleExample

enter

nums[] = {10, 8, 7, 60, 20, 18, 30, 60}; m = 3; x[] = {1, 2, 5}; y[] = {500, 10, 2};

Output

708

Explanation − Let’s perform each operation one by one.

• In the first operation, we will replace 7 elements with 500. So, the array becomes {10, 8, 500, 60, 20, 18, 30, 60}.

• In the second operation, we can replace up to 2 elements with 10, but we only have 1 element less than 10. So, we replace 8 with 10 and the array becomes {10, 10, 500, 60, 20, 18, 30, 60}.

• In the third operation, we can replace up to 5 elements with 2, but there are no elements less than 2 in the array. Therefore, we will not replace any elements.

enter

nums[] = {30, 40, 50, 50, 60}; m = 3; x[] = {2, 3, 6}; y[] = {10, 8, 21};

Output

230

Explanation − All elements of the y[] array are smaller than the elements of the original array. Therefore, we don't need to replace any element of the given array to get the maximum sum.

enter

nums[] = {30, 40, 50, 50, 60}; m = 3; x[] = {2, 4, 5}; y[] = {50, 60, 100};

Output

500

Explanation − Here, we can replace up to x[p] elements in each operation. In the last operation, we can replace each element in the array with 100, resulting in a maximum sum equal to 100.

method one

In this method, we will iterate over the x[] and y[] arrays. In each iteration, we will sort the array to get at most x[p] array elements that are smaller than y[p] elements and replace them with y[p].

algorithm

Step 1 − Initialize ‘maxSum’ to 0, which is used to store the maximum sum of array elements.

Step 2 − Start traversing the x[] and y[] array elements.

Step 3 − Store the value of x[p] in a temporary variable and sort the nums[] array.

Step 4− Start traversing the sorted array within the loop.

Step 5 − If the temperature is greater than 0 and nums[q] is less than y[p], update nums[q] with y[p] and decrement the temp value by 1.

Step 6− Outside the loop, start traversing the updated array, take out the sum of all array elements and store it in the maxSum variable.

Step 7 − Return maxSum at the end of the function.

Example

#include <bits/stdc++.h>
using namespace std;

int getMaxSum(int nums[], int n, int q, int x[], int y[]) {
    int maxSum = 0;
    // Traverse X[] and Y[] array
    for (int p = 0; p < q; p++) {
        // Replacing x[p] number of elements of nums[] array with y[p] if they are lesser than y[p]
        int temp = x[p];
        sort(nums, nums + n);
        for (int q = 0; q < n; q++) {
            if (temp > 0 && nums[q] < y[p]) {
                nums[q] = y[p];
                temp--;
            }
        }
    }
    // Sum of the array
    for (int p = 0; p < n; p++) {
        maxSum += nums[p];
    }
    return maxSum;
}
int main() {
    int nums[] = {10, 8, 7, 60, 20, 18, 30, 60};
    int n = (sizeof nums) / (sizeof nums[0]);
    int m = 3;
    int x[] = {1, 2, 5};
    int y[] = {500, 10, 2};
    cout << "The maximum sum we can get by replacing the array values is " << getMaxSum(nums, n, m, x, y);
    return 0;
}

Output

The maximum sum we can get by replacing the array values is 708

Time complexity− O(M*NlogN), where O(M) is used to traverse all queries and O(NlogN) is used to sort the array.

Space complexity− For sorting an array, the space complexity is O(N).

Method Two

In this approach, we will use a priority queue to store pairs of array elements and their occurrence times.

For example, we will push the {nums[p], 1} pair into the priority queue for each array element. At the same time, we push the pair {y[p], x[p]} into the priority queue. In a priority queue, pairs will be sorted based on the first element. Therefore, we can take the top N elements from the queue. Here, for the pair {y[p],x[p]}, we can take out the y[p] elements x[p] times, and we need to take out a total of N elements to maximize the sum.

algorithm

Step 1 − Initialize the ‘maxSum’ with 0 and the priority queue to store the pair of elements and their number of occurrences.

Step 2− For all array elements, insert {nums[p], 1} pairs into the queue.

Step 3 − Then, insert the {y[p], x[p]} pair into the priority queue.

Step 4− Iterate until n is greater than 0.

Step 4.1 − Remove the first element from the priority queue.

Step 4.2 − Add first_ele * max(n, second_ele) to the sum. Here, we use max(n, second_ele) to handle the last case.

Step 4.3 − Subtract second_ele from n.

Step 5− Return maxSum.

Example

#include <bits/stdc++.h>
using namespace std;

int getMaxSum(int nums[], int n, int m, int x[], int y[]) {
    int maxSum = 0, p;
    // To get maximum sum
    priority_queue<pair<int, int>> p_que;
    // Insert nums[] array pairs into the queue
    for (p = 0; p < n; p++)
        p_que.push({nums[p], 1});
    // Push replacement pairs
    for (p = 0; p < m; p++)
        p_que.push({y[p], x[p]});
    // Add the first N elements of the priority queue in the sum
    while (n > 0) {
        // Get top element of priority queue
        auto temp = p_que.top();
        // Remove top element
        p_que.pop();
        // Add value to the sum
        maxSum += temp.first * min(n, temp.second);
        // Change N
        n -= temp.second;
    }
    return maxSum;
}
int main() {
    int nums[] = {10, 8, 7, 60, 20, 18, 30, 60};
    int n = (sizeof nums) / (sizeof nums[0]);
    int m = 3;
    int x[] = {1, 2, 5};
    int y[] = {500, 10, 2};
    cout << "The maximum sum we can get by replacing the array values is " << getMaxSum(nums, n, m, x, y);
    return 0;
}

Output

The maximum sum we can get by replacing the array values is 708

Time complexity - O(N*logN m*logm), where O(N) and O(m) are used to traverse the given array, and O(logN) are used to insert and delete elements in the queue.

Space complexity - O(N M) for storing pairs in the queue.

In the first method, we need to sort the array in each iteration to find the smallest x[p] elements. Use a priority queue to automatically sort elements as they are inserted or removed because it uses the heap data structure. Therefore, it improves the performance of your code.

The above is the detailed content of Maximum possible array sum after performing the given operation. For more information, please follow other related articles on the PHP Chinese website!