我们将得到一个数组，必须从中选择一个元素并将该元素添加到总和中。将该元素添加到总和中后，我们必须从数组中删除三个元素（如果存在当前数字、当前数字 -1 和当前数字 + 1）。通过此方法，我们将使数组为空并得到总和。最后，我们必须使总和最大。
Input: [ 1, 2, 3]Output: 4
登录后复制
说明
一开始，我们可以有 3 步，删除 1、2 或 3。
让我们删除 1，然后我们必须删除 0、1 和 2（如果存在其中任何一个，则必须至少存在其中一个）。我们将得到总和等于 1，数组将只剩下 3。删除 3 后，我们将得到总和等于 4。
让我们删除 2，然后我们必须删除 1、2 和 3，最终的总和将为 2。
先删除 3，那么 sum 为 3，数组为 1。删除 1 后，sum 为 4。
Input: [ 1, 2, 2, 2, 3, 3]Output: 8
登录后复制
我们可以删除前两个三，这将给我们 6，然后两个二将被删除。
之后我们将删除剩下的两个中的一个并得到 8 作为答案。
方法 1
在这种方法中，我们将首先获取数组中存在的最大元素，以获取数组中存在的元素的频率。
稍后我们将创建一个数组来存储给定数组中存在的元素的频率。
我们将从频率数组的最后一个元素开始遍历，因为我们必须从数组中删除当前的一个减号和一个加号元素，这将始终保存比其大一的数字，从而得到最大总和：结果。
示例
#include using namespace std;int maxElement(int arr[], int n){ int mx = arr[0]; // defining variable to store the maximum element for(int i=1; i0; 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: 8
登录后复制
时间和空间复杂度
上述代码的时间复杂度为 O(N)，其中 N 是给定数组中存在的最大元素。
上述代码的空间复杂度与时间复杂度相同，均为 O(N)，因为我们创建了一个数组来存储元素的频率。
前面给出的方法有一个问题，如果最大元素非常大，则需要大量时间和空间来解决问题。为了解决这个问题，我们有下一个方法。
地图方法
在这种方法中，我们将创建映射来存储元素的频率而不是数组，想法是相同的。
示例
#include 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_mapmp; // 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: 8
登录后复制
时间和空间复杂度
上述代码的时间复杂度为 O(N)，其中 N 是给定数组中存在的元素数量。
上述代码的空间复杂度与时间复杂度相同，均为 O(N)，因为我们创建了一个映射来存储元素的频率。
结论
在本教程中，我们实现了一个 C++ 程序，用于最大化数组中所选数字的总和，使其为空。我们必须从中选择一个元素并将该元素添加到总和中。将该元素添加到总和中后，如果存在当前数、当前数-1和当前数+1，我们必须从数组中删除三个元素。我们已经实现了两种具有线性时间和空间复杂度的频率基础方法。 p>
以上就是将以下内容翻译为中文：最大化从数组中选择的数字的和，使其变为空的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2585344.html
