從陣列中選擇數字並求和，直到陣列為空

---

給定一個數組，我們需要從中選擇一個元素並將其新增到總和中。將該元素新增到總和後，如果存在當前數字、當前數字減 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)，因為我們建立了一個對映來儲存元素的頻率。

結論

在本教程中，我們實現了一個 C++ 程式，用於最大化從陣列中選擇的數字的總和，以使其為空。我們需要從中選擇一個元素並將其新增到總和中。將該元素新增到總和後，如果存在當前數字、當前數字減 1 和當前數字加 1，則需要從陣列中刪除這三個元素。我們已經實現了兩種基於頻率的方法，具有線性時間和空間複雜度。