Traduisez ce qui suit en chinois : Maximisez la somme des nombres sélectionnés dans un tableau afin qu'il devienne vide

Nous obtiendrons un tableau dans lequel nous devrons sélectionner un élément et ajouter cet élément à la somme. Après avoir ajouté cet élément à la somme, nous devons supprimer trois éléments du tableau (numéro actuel, numéro actuel -1 et numéro actuel + 1 s'il est présent). Avec cette méthode, nous rendrons le tableau vide et obtiendrons la somme. Enfin, il faut maximiser la somme.

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

Instructions

Au début, on peut avoir 3 étapes, supprimer 1, 2 ou 3.

• Supprimons 1, puis nous devons supprimer 0, 1 et 2 (si l'un d'entre eux est présent, au moins l'un d'entre eux doit être présent). Nous obtiendrons la somme égale à 1 et le tableau n’en aura que 3. Après avoir supprimé 3, on obtient une somme égale à 4.

• Supprimons 2, puis nous devons supprimer 1, 2 et 3 et la somme finale sera de 2.

• Supprimez d'abord 3, puis la somme est 3 et le tableau est 1. Après avoir supprimé 1, la somme est 4.

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

Nous pouvons supprimer les deux premiers trois, ce qui nous donnera 6, puis les deux deux seront supprimés.

Ensuite, nous supprimerons l'un des deux restants et obtiendrons 8 comme réponse.

Méthode 1

Dans cette méthode, nous obtiendrons d'abord le maximum d'éléments présents dans le tableau pour obtenir la fréquence des éléments présents dans le tableau.

Plus tard, nous créerons un tableau pour stocker la fréquence des éléments présents dans un tableau donné.

Nous commencerons à parcourir à partir du dernier élément du tableau de fréquences, car nous devons supprimer l'élément actuel moins et un élément plus du tableau, qui contiendra toujours un nombre supérieur à lui, donnant la somme maximale : résultat.

Exemple

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

Sortie

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

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N), où N est le plus grand élément présent dans le tableau donné.

La complexité spatiale du code ci-dessus est la même que la complexité temporelle, qui est O(N), car nous créons un tableau pour stocker la fréquence des éléments.

La méthode donnée précédemment a un problème, si le plus grand élément est très grand, il faut beaucoup de temps et d'espace pour résoudre le problème. Pour résoudre ce problème, nous avons la méthode suivante.

Méthode cartographique

Dans cette approche, nous allons créer une carte pour stocker la fréquence des éléments au lieu d'un tableau, l'idée est la même.

Exemple

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

Sortie

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

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N), où N est le nombre d'éléments présents dans le tableau donné.

La complexité spatiale du code ci-dessus est la même que la complexité temporelle, qui est O(N), car nous créons une carte pour stocker la fréquence des éléments.

Conclusion

Dans ce tutoriel, nous avons implémenté un programme C++ pour maximiser la somme des nombres sélectionnés dans un tableau, le rendant vide. Nous devons en sélectionner un élément et ajouter cet élément à la somme. Après avoir ajouté cet élément à la somme, nous devons supprimer trois éléments du tableau s'il y a le numéro actuel, le numéro actuel -1 et le numéro actuel +1. Nous avons implémenté deux méthodes basées sur la fréquence avec une complexité temporelle et spatiale linéaire. p>

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!