將以下內容翻譯為中文：最大化從數組中選擇的數字的和，使其變為空

我們將得到一個數組，必須從中選擇一個元素並將該元素加入總和中。將該元素新增至總和後，我們必須從陣列中刪除三個元素（如果存在當前數字、目前數字 -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>

以上是將以下內容翻譯為中文：最大化從數組中選擇的數字的和，使其變為空的詳細內容。更多資訊請關注PHP中文網其他相關文章！