我們將得到一個數組，必須從中選擇一個元素並將該元素加入總和中。將該元素新增至總和後，我們必須從陣列中刪除三個元素（如果存在當前數字、目前數字 -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 作為答案。
在這種方法中，我們將首先獲取數組中存在的最大元素，以獲取數組中存在的元素的頻率。
稍後我們將建立一個陣列來儲存給定陣列中存在的元素的頻率。
我們將從頻率數組的最後一個元素開始遍歷，因為我們必須從數組中刪除當前的一個減號和一個加號元素，這將始終保存比其大一的數字，從而得到最大總和：結果。
#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>
以上是將以下內容翻譯為中文：最大化從數組中選擇的數字的和，使其變為空的詳細內容。更多資訊請關注PHP中文網其他相關文章！
