Übersetzen Sie Folgendes ins Chinesische: Maximieren Sie die Summe der aus einem Array ausgewählten Zahlen, sodass es leer wird

Wir erhalten ein Array, aus dem wir ein Element auswählen und dieses Element zur Summe hinzufügen müssen. Nachdem wir dieses Element zur Summe hinzugefügt haben, müssen wir drei Elemente aus dem Array entfernen (aktuelle Zahl, aktuelle Zahl -1 und aktuelle Zahl + 1, falls vorhanden). Mit dieser Methode machen wir das Array leer und erhalten die Summe. Schließlich müssen wir die Summe maximieren.

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

Anleitung

Am Anfang können wir 3 Schritte haben und 1, 2 oder 3 löschen.

• Entfernen wir 1, dann müssen wir 0, 1 und 2 entfernen (wenn einer von ihnen vorhanden ist, muss mindestens einer von ihnen vorhanden sein). Wir erhalten die Summe gleich 1 und das Array bleibt mit nur 3 übrig. Nachdem wir 3 entfernt haben, erhalten wir eine Summe von 4.

• Entfernen wir 2, dann müssen wir 1, 2 und 3 entfernen und die Endsumme ist 2.

• Löschen Sie zuerst 3, dann ist die Summe 3 und das Array ist 1. Nach dem Entfernen von 1 beträgt die Summe 4.

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

Wir können die ersten beiden Dreien entfernen, was uns 6 ergibt, und dann werden die beiden Zweien entfernt.

Danach löschen wir einen der verbleibenden beiden und erhalten als Antwort 8.

Methode 1

Bei dieser Methode ermitteln wir zunächst das maximale Element im Array, um die Häufigkeit der im Array vorhandenen Elemente zu ermitteln.

Später erstellen wir ein Array, um die Häufigkeit der in einem bestimmten Array vorhandenen Elemente zu speichern.

Wir beginnen mit dem Durchlaufen des letzten Elements des Frequenzarrays, da wir das aktuelle ein Minus- und ein Pluselement aus dem Array entfernen müssen, das immer eine um eins größere Zahl enthalten wird, was das maximale Summenergebnis ergibt.

Beispiel

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

Ausgabe

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

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N), wobei N das größte im gegebenen Array vorhandene Element ist.

Die räumliche Komplexität des obigen Codes ist dieselbe wie die zeitliche Komplexität, die O(N) ist, da wir ein Array erstellen, um die Häufigkeit der Elemente zu speichern.

Die zuvor angegebene Methode weist ein Problem auf: Wenn das größte Element sehr groß ist, ist viel Zeit und Platz erforderlich, um das Problem zu lösen. Um dieses Problem zu lösen, haben wir die nächste Methode.

Kartenmethode

Bei dieser Methode erstellen wir eine Karte, um die Häufigkeit von Elementen anstelle eines Arrays zu speichern. Die Idee ist dieselbe.

Beispiel

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

Ausgabe

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

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N), wobei N die Anzahl der im angegebenen Array vorhandenen Elemente ist.

Die räumliche Komplexität des obigen Codes ist dieselbe wie die zeitliche Komplexität, die O(N) ist, da wir eine Karte erstellen, um die Häufigkeit von Elementen zu speichern.

Fazit

In diesem Tutorial haben wir ein C++-Programm implementiert, um die Summe ausgewählter Zahlen in einem Array zu maximieren und es leer zu machen. Wir müssen daraus ein Element auswählen und dieses Element zur Summe hinzufügen. Nachdem wir dieses Element zur Summe hinzugefügt haben, müssen wir drei Elemente aus dem Array entfernen, wenn es die aktuelle Zahl, die aktuelle Zahl -1 und die aktuelle Zahl +1 gibt. Wir haben zwei frequenzbasierte Methoden mit linearer Zeit- und Raumkomplexität implementiert. p>

Das obige ist der detaillierte Inhalt vonÜbersetzen Sie Folgendes ins Chinesische: Maximieren Sie die Summe der aus einem Array ausgewählten Zahlen, sodass es leer wird. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!