En C++, maximiser la somme d'un tableau en multipliant son préfixe par -1

Nous avons un tableau d'entiers et la tâche est d'abord d'obtenir le préfixe du tableau puis de le multiplier par -1, ensuite de calculer la somme des préfixes du tableau et enfin de trouver la somme maximale dans le préfixe généré tableau.

Le tableau de préfixes est généré comme suit :

Le premier élément du tableau de préfixes prefixArray[0] = le premier élément du tableau

Le deuxième élément du tableau de préfixes prefixArray[1] = prefixArray[0] + arr [1]

Le troisième élément du tableau de préfixes prefixArray[2] = prefixArray[1] + arr[2]

Le quatrième élément du tableau de préfixes prefixArray[3] = prefixArray[2] + arr[3] . ..etc. attends.

Regardons les différentes situations d'entrée et de sortie de ce problème -

Pour int arr[] = {2, 4, 1, 5, 2}

Le tableau de préfixes de sortie est : -2 2 3 8 10 Maximisez la somme d'un tableau en multipliant son préfixe par -1 : 21

Explication - Nous avons un tableau d'entiers. Nous obtenons d’abord le préfixe du tableau, qui est 2, et le multiplions par -1. Le nouveau tableau est donc {-2, 4, 1, 5, 2}. Maintenant, nous allons former la somme maximale du tableau de préfixes.

Le tableau de préfixes est {-2, 2, 3, 8, 10}. La dernière étape consiste à maximiser la somme à -2+2+3+8+`0 = 21, qui est le résultat final.

Dans - int arr[] = {-1, 4, 2, 1, -9, 6};

La sortie - tableau de préfixes est : 1 5 7 8 -1 5 En combinant le préfixe de le tableau avec Multiplié par -1, la somme des tableaux maximisés est : 19

Explication- Nous avons un tableau d'entiers. Nous prenons d’abord le préfixe du tableau -1 et le multiplions par -1. Ainsi, le nouveau tableau sera {1, 4, 2, 1, -9, 6}. Maintenant, nous allons former Le tableau de préfixes est {1, 5, 7, 8, -1, 5}. La dernière étape consiste à maximiser la somme à 1+5+8+5 = 19, qui est le résultat final.

La méthode utilisée dans le programme ci-dessous est la suivante −

• Déclarez un tableau d'entiers et une variable temporaire x comme -1, puis définissez arr[0] sur arr[0] * x.

• Calculez la taille du tableau. Déclarez un tableau de préfixes prefix_array[size]. Appelez la fonction create_prefix_arr(arr, size, prefix_array) pour générer un tableau de préfixes pour le tableau donné. L'impression du tableau de préfixes

• appelle la fonction maximise_sum(prefix_array, size), qui stockera la somme maximale du tableau.

• À l'intérieur de la fonction void create_prefix_arr(int arr[], int size, int prefix_array[])

  • définissez prefix_array[0] sur arr[0].

  • Commencez à boucler de i à 0 jusqu'à la taille du tableau. À l'intérieur de la boucle, définissez prefix_array[i] sur prefix_array[i-1] + arr[i].

• À l'intérieur de la fonction int maximise_sum(int prefix_array[], int size)

  • déclarez une variable temporaire temp et définissez-la sur -1.

  • Commencez à boucler de i à 0 jusqu'à la taille du tableau. Dans la boucle, définissez temp sur max(temp, prefix_array[i])

  • Déclarez un tableau arr[temp +1] et initialisez tous les éléments du tableau à 0.

  • Commencez à boucler de i à 0 jusqu'à la taille du tableau. Dans la boucle, déclarez une variable temporaire max_sum arr[prefix_array[i]]++

  • et définissez-la sur 0. Déclarez une variable i comme temp

  • pour démarrer la boucle lorsque i>0. Vérifiez si arr[i] > 0, puis définissez max_sum sur max_sum + i, et définissez arr[i-1]-- et arr[i]--. Sinon, décrémentez i de 1.

  • Renvoyer max_sum.

Exemple

#include <bits/stdc++.h>
using namespace std;
#define Max_size 5
//create the prefix array
void create_prefix_arr(int arr[], int size, int prefix_array[]) {
   prefix_array[0] = arr[0];
   for(int i=0; i<size; i++)  {
      prefix_array[i] = prefix_array[i-1] + arr[i];
   }
}
//find the maximum sum of prefix array
int maximize_sum(int prefix_array[], int size) {
   int temp = -1;
   for(int i = 0; i < size; i++) {
      temp = max(temp, prefix_array[i]);
   }
   int arr[temp + 1];
   memset(arr, 0, sizeof(arr));

   for(int i = 0; i < size; i++) {
      arr[prefix_array[i]]++;
   }
   int max_sum = 0;
   int i = temp;
   while(i>0) {
      if(arr[i] > 0) {
         max_sum = max_sum + i;
         arr[i-1]--;
         arr[i]--;
      } else {
         i--;
      }
   }
   return max_sum;
}

int main() {
   int arr[] = {2, 4, 1, 5, 2};
      int x = -1;
      arr[0] = arr[0] * x;
      int size = sizeof(arr) / sizeof(arr[0]);
   int prefix_array[size];

   //call function to create a prefix array
   create_prefix_arr(arr, size, prefix_array);
   //print the prefix array
   cout<<"Prefix array is: ";
   for(int i = 0; i < size; i++) {
      cout << prefix_array[i] << " ";
   }
   //print the maximum sum of prefix array
   cout<<"\nMaximize the sum of array by multiplying prefix of array with -1 are:" <<maximize_sum(prefix_array, size);
   return 0;
}

Output

Si nous exécutons le code ci-dessus, la sortie suivante sera générée

Prefix array is: -2 2 3 8 10
Maximize the sum of array by multiplying prefix of array with -1 are: 21

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!