从数组中选择数字并求和,直到数组为空
给定一个数组,我们需要从中选择一个元素并将其添加到总和中。将该元素添加到总和后,如果存在当前数字、当前数字减 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),因为我们创建了一个映射来存储元素的频率。
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,则需要从数组中删除这三个元素。我们已经实现了两种基于频率的方法,具有线性时间和空间复杂度。