从数组中选择数字并求和，直到数组为空

---

给定一个数组，我们需要从中选择一个元素并将其添加到总和中。将该元素添加到总和后，如果存在当前数字、当前数字减 1 和当前数字加 1，则需要从数组中删除这三个元素。通过这种方法，我们将使数组为空并得到一个总和。最后，我们需要使总和最大化。

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

解释

首先，我们可以有三种操作：删除 1、2 或 3。

• 让我们删除 1，然后我们需要删除 0、1 和 2（如果它们中的任何一个存在，至少其中一个必须存在）。我们将得到总和等于 1，数组将只剩下 3。删除 3 后，我们将得到总和等于 4。

• 让我们删除 2，然后我们需要删除 1、2 和 3，最终总和将为 2。

• 让我们首先删除 3，然后总和将为 3，数组将为 1。删除 1 后，我们将得到总和为 4。

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

我们可以先删除两个 3，这将给我们 6，并且两个 2 将随之被删除。

之后，我们将删除剩余的一个 2，得到答案 8。

方法 1

在这种方法中，我们将首先获取数组中存在的最大元素，以获取数组中存在的元素的频率。

稍后，我们将创建一个数组来存储给定数组中存在的元素的频率。

我们将从频率数组的最后一个元素遍历，因为我们需要从数组中删除当前元素、减 1 和加 1 的元素，这将始终保存比当前元素大 1 的数字，从而导致结果为最大和。

示例

#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);
}

输出

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

时间和空间复杂度

上述代码的时间复杂度为 O(N)，其中 N 是给定数组中存在最大元素。

上述代码的空间复杂度与时间复杂度相同，即 O(N)，因为我们创建了一个数组来存储元素的频率。

之前给出的方法有一个问题，如果最大元素非常大，那么解决问题将需要大量时间和空间。为了解决这个问题，我们有以下方法。

映射方法

在这种方法中，我们将创建映射来存储元素的频率，而不是数组，并且思路相同。

示例

#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);
}

输出

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

时间和空间复杂度

上述代码的时间复杂度为 O(N)，其中 N 是给定数组中存在的元素数量。

上述代码的空间复杂度与时间复杂度相同，即 O(N)，因为我们创建了一个映射来存储元素的频率。

结论

在本教程中，我们实现了一个 C++ 程序，用于最大化从数组中选择的数字的总和，以使其为空。我们需要从中选择一个元素并将其添加到总和中。将该元素添加到总和后，如果存在当前数字、当前数字减 1 和当前数字加 1，则需要从数组中删除这三个元素。我们已经实现了两种基于频率的方法，具有线性时间和空间复杂度。