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