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


给定一个数组,我们需要从中选择一个元素并将其添加到总和中。将该元素添加到总和后,如果存在当前数字、当前数字减 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 的数字,从而导致结果为最大和。

示例

Open Compiler
#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),因为我们创建了一个数组来存储元素的频率。

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

映射方法

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

示例

Open Compiler
#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),因为我们创建了一个映射来存储元素的频率。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

结论

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

更新于: 2023年5月16日

136 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始
广告