Terjemah yang berikut ke dalam bahasa Cina: Maksimumkan jumlah nombor yang dipilih daripada tatasusunan supaya ia menjadi kosong

Kami akan mendapat tatasusunan yang mana kami perlu memilih elemen dan menambah elemen itu pada jumlah. Selepas menambah elemen ini kepada jumlah, kita perlu mengeluarkan tiga elemen daripada tatasusunan (nombor semasa, nombor semasa -1 dan nombor semasa + 1 jika ada). Dengan kaedah ini kita akan membuat tatasusunan kosong dan mendapatkan jumlahnya. Akhirnya, kita mesti memaksimumkan jumlahnya.

Input: [ 1, 2, 3]
Output: 4 

Arahan

Pada mulanya, kita boleh ada 3 langkah, padam 1, 2 atau 3.

• Jom keluarkan 1, lepas tu kena buang 0, 1 dan 2 (kalau ada yang ada, sekurang-kurangnya salah satu mesti ada). Kami akan mendapat jumlah yang sama dengan 1 dan tatasusunan akan ditinggalkan dengan hanya 3. Selepas mengeluarkan 3, kita mendapat jumlah yang sama dengan 4.

• Mari kita keluarkan 2, kemudian kita perlu mengeluarkan 1, 2 dan 3 dan jumlah akhir ialah 2.

• Padam 3 dahulu, kemudian jumlahnya ialah 3 dan tatasusunan ialah 1. Selepas mengeluarkan 1, jumlah ialah 4.

Input: [ 1, 2, 2, 2, 3, 3]
Output: 8

Kita boleh mengalih keluar dua tiga yang pertama, yang akan memberi kita 6, dan kemudian dua dua akan dialih keluar.

Selepas itu kami akan memadamkan satu daripada dua yang tinggal dan mendapat 8 sebagai jawapan.

Kaedah 1

Dalam kaedah ini kita akan mula-mula mendapatkan elemen maksimum yang terdapat dalam tatasusunan untuk mendapatkan kekerapan unsur-unsur yang hadir dalam tatasusunan.

Kemudian kami akan mencipta tatasusunan untuk menyimpan kekerapan elemen yang hadir dalam tatasusunan yang diberikan.

Kami akan mula merentasi dari elemen terakhir tatasusunan kekerapan, kerana kami perlu mengalih keluar elemen satu tolak dan satu tambah semasa daripada tatasusunan, yang akan sentiasa memegang nombor satu lebih besar daripadanya, sekali gus memberikan hasil jumlah maksimum: hasil.

Contoh

#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);
}

Output

The maximum sum we can get by deleting the elements is: 8

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N), dengan N ialah elemen terbesar yang terdapat dalam tatasusunan yang diberikan.

Kerumitan ruang kod di atas adalah sama dengan kerumitan masa, iaitu O(N), kerana kami mencipta tatasusunan untuk menyimpan kekerapan elemen.

Cara yang diberikan tadi ada masalah, jika elemen terbesar sangat besar, ia mengambil masa dan ruang yang banyak untuk menyelesaikan masalah. Untuk menyelesaikan masalah ini, kami mempunyai kaedah seterusnya.

Kaedah peta

Dalam kaedah ini kita akan mencipta peta untuk menyimpan kekerapan elemen dan bukannya tatasusunan, ideanya adalah sama.

Contoh

#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);
}

Output

The maximum sum we can get by deleting the elements is: 8

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N), dengan N ialah bilangan elemen yang terdapat dalam tatasusunan yang diberikan.

Kerumitan ruang kod di atas adalah sama dengan kerumitan masa, iaitu O(N), kerana kami mencipta peta untuk menyimpan kekerapan elemen.

Kesimpulan

Dalam tutorial ini, kami melaksanakan program C++ untuk memaksimumkan jumlah nombor yang dipilih dalam tatasusunan, menjadikannya kosong. Kita perlu memilih elemen daripadanya dan menambah elemen itu kepada jumlah. Selepas menambah elemen ini kepada jumlah, kita perlu mengalih keluar tiga elemen daripada tatasusunan jika terdapat nombor semasa, nombor semasa -1 dan nombor semasa +1. Kami telah melaksanakan dua kaedah berasaskan frekuensi dengan masa linear dan kerumitan ruang. p>

Atas ialah kandungan terperinci Terjemah yang berikut ke dalam bahasa Cina: Maksimumkan jumlah nombor yang dipilih daripada tatasusunan supaya ia menjadi kosong. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!