Translate the following into Chinese: Maximize the sum of numbers selected from an array so that it becomes empty

We will get an array from which we have to select an element and add that element to the sum. After adding this element to the sum, we have to remove three elements from the array (current number, current number -1 and current number 1 if present). With this method we will make the array empty and get the sum. Finally, we must maximize the sum.

Input: [ 1, 2, 3]
Output: 4 

illustrate

At the beginning, we can have 3 steps, delete 1, 2 or 3.

• Let's remove 1, then we have to remove 0, 1 and 2 (if any of them are present, at least one of them must be present). We will get the sum equal to 1 and the array will be left with only 3. After removing 3, we get a sum equal to 4.

• Let's remove 2, then we have to remove 1, 2 and 3 and the final sum will be 2.

• Delete 3 first, then the sum is 3 and the array is 1. After removing 1, sum is 4.

Input: [ 1, 2, 2, 2, 3, 3]
Output: 8

We can remove the first two threes, which will give us 6, and then the two twos will be removed.

Afterwards we will remove one of the remaining two and get 8 as the answer.

method 1

In this method we will first get the maximum element present in the array to get the frequency of elements present in the array.

Later we will create an array to store the frequency of elements present in a given array.

We will start traversing from the last element of the frequency array, since we have to remove the current one minus and one plus element from the array, which will always hold a number one greater than it, giving the maximum sum: result .

Example

#include <iostream>
using namespace std;
int maxElement(int arr[], int n){
   int mx = arr[0]; // defining variable to store the maximum element
   for(int i=1; i<n; i++){
      if(mx < arr[i]){
         mx = arr[i];
      }
   }
   return mx;
}
int maxSum(int arr[], int n){
   // getting the maximum element first 
   int mx = maxElement(arr,n);
   // creating array of maximum size to store frequecny of the elements 
   int freq[mx+1] = {0}; // defining each element as zero first 
   // getting the frequecny of the elements 
   for(int i=0; i<n; i++){
      freq[arr[i]]++;
   }
   int ans = 0; // variable to store the answer 
   // traversing over the array 
   for(int i=mx; i>0; i--){
      if(freq[i] > 0){
         ans += freq[i]*i;
         freq[i-1] -= freq[i];
      }
   }
   return ans;
}
int main(){
   int n; // number of elements in the given array 
   int arr[] = { 1, 2, 2, 2, 3, 3}; // given array
   n = sizeof(arr)/sizeof(arr[0]);
   // calling the function to get the answer 
   cout<<"The maximum sum we can get by deleting the elements is: "<<maxSum(arr,n);
}

Output

The maximum sum we can get by deleting the elements is: 8

Time and space complexity

The time complexity of the above code is O(N), where N is the largest element present in the given array.

The space complexity of the above code is the same as the time complexity, both are O(N), because we create an array to store the frequency of elements.

There is a problem with the method given earlier. If the largest element is very large, it will take a lot of time and space to solve the problem. To solve this problem, we have the next method.

Map method

In this approach we will create a map to store the frequency of elements instead of an array, the idea is the same.

Example

#include <bits/stdc++.h>
using namespace std;
int maxSum(int arr[], int n){
   // sorting the array to travers over the map from last 
   sort(arr,arr+n);
   // creating the map 
   unordered_map<int,int>mp;
   // getting the frequecny of the elements 
   for(int i=n-1; i>=0; i--){
      mp[arr[i]]++;
   }
   int ans = 0; // variable to store the answer 
   // traversing over the array 
   for(int i=n-1; i>=0; i--){
      if (mp.count(arr[i])) {
         ans += arr[i];
         mp[arr[i]]--;
         // if element frequency in map become zero
         // than remove that element
         if (mp[arr[i]] == 0){
            mp.erase(arr[i]);
         }
         if (mp.count(arr[i] - 1)){
            mp[arr[i] - 1]--;
            if (mp[arr[i] - 1] == 0){
               mp.erase(arr[i] - 1);
            }
         }
      }
   }
   return ans;
}
int main(){
   int n; // number of elements in the given array 
   int arr[] = { 1, 2, 2, 2, 3, 3}; // given array
   n = sizeof(arr)/sizeof(arr[0]);
   // calling the function to get the answer 
   cout<<"The maximum sum we can get by deleting the elements is: "<<maxSum(arr,n);
}

Output

The maximum sum we can get by deleting the elements is: 8

Time and space complexity

The time complexity of the above code is O(N), where N is the number of elements present in the given array.

The space complexity of the above code is the same as the time complexity, which is O(N), because we create a map to store the frequency of elements.

in conclusion

In this tutorial, we implemented a C program that maximizes the sum of selected numbers in an array, making it empty. We have to select an element from it and add that element to the sum. After adding this element to the sum, we have to remove three elements from the array if there are current number, current number -1 and current number 1. We have implemented two frequency-based methods with linear time and space complexity. p>

The above is the detailed content of Translate the following into Chinese: Maximize the sum of numbers selected from an array so that it becomes empty. For more information, please follow other related articles on the PHP Chinese website!