</p><p>我们将得到一个数组,必须从中选择一个元素并将该元素添加到总和中。将该元素添加到总和中后,我们必须从数组中删除三个元素(如果存在当前数字、当前数字 -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 <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,我们必须从数组中删除三个元素。我们已经实现了两种具有线性时间和空间复杂度的频率基础方法。 p>