首頁 > 後端開發 > C++ > 主體

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

WBOY
發布: 2023-08-29 11:25:14
轉載
1104 人瀏覽過

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

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

來源:tutorialspoint.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板