Maximieren Sie in C++ die Summe eines Arrays, indem Sie sein Präfix mit -1 multiplizieren

Wir haben ein Array von Ganzzahlen und die Aufgabe besteht darin, zuerst das Präfix des Arrays zu ermitteln und es dann mit -1 zu multiplizieren, zweitens die Summe der Präfixe des Arrays zu berechnen und schließlich die maximale Summe im generierten Präfix zu finden Array.

Das Präfix-Array wird wie folgt generiert:

Das erste Element des Präfix-Arrays prefixArray[0] = das erste Element des Arrays

Das zweite Element des Präfix-Arrays prefixArray[1] = prefixArray[0] + arr [1]

Das dritte Element des Präfix-Arrays prefixArray[2] = prefixArray[1] + arr[2]

Das vierte Element des Präfix-Arrays prefixArray[3] = prefixArray[2] + arr[3] . ..etc. warte.

Sehen wir uns die verschiedenen Eingabe- und Ausgabesituationen dieses Problems an -

Für int arr[] = {2, 4, 1, 5, 2}

Das Ausgabe--Präfix-Array lautet: -2 2 3 8 10 Maximieren Sie die Summe eines Arrays, indem Sie sein Präfix mit -1 multiplizieren: 21

Erklärung – Wir haben ein Array von ganzen Zahlen. Zuerst erhalten wir das Präfix des Arrays, das 2 ist, und multiplizieren es mit -1. Das neue Array ist also {-2, 4, 1, 5, 2}. Nun bilden wir die maximale Summe des Präfix-Arrays.

Das Präfix-Array ist {-2, 2, 3, 8, 10}. Der letzte Schritt besteht darin, die Summe auf -2+2+3+8+`0 = 21 zu maximieren, was der endgültigen Ausgabe entspricht.

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

Das ausgegebene - Präfix-Array lautet: 1 5 7 8 -1 5 Durch Kombinieren des Präfixes von Das Array mit Multipliziert mit -1 beträgt die Summe der maximierten Arrays: 19

Erklärung- Wir haben ein Array von ganzen Zahlen. Zuerst nehmen wir das Präfix des Arrays -1 und multiplizieren es mit -1. Das neue Array wird also {1, 4, 2, 1, -9, 6} sein. Jetzt werden wir formieren Das Präfixarray ist {1, 5, 7, 8, -1, 5}. Der letzte Schritt besteht darin, die Summe auf 1+5+8+5 = 19 zu maximieren, was der endgültigen Ausgabe entspricht.

Die im folgenden Programm verwendete Methode lautet wie folgt: -

• Deklarieren Sie ein ganzzahliges Array und eine temporäre Variable x als -1 und setzen Sie dann arr[0] auf arr[0] * x.

• Berechnen Sie die Größe des Arrays. Deklarieren Sie ein Präfix-Array prefix_array[size]. Rufen Sie die Funktion create_prefix_arr(arr, size, prefix_array) auf, um ein Präfix-Array für das angegebene Array zu generieren. Drucken des Präfix-Arrays

• ruft die Funktion maximieren_sum(präfix_array, größe) auf, die die maximale Summe des Arrays speichert.

• Innerhalb der Funktion void create_prefix_arr(int arr[], int size, int prefix_array[])

  • setze prefix_array[0] auf arr[0].

  • Beginnen Sie mit der Schleife von i bis 0, bis die Größe des Arrays erreicht ist. Setzen Sie innerhalb der Schleife prefix_array[i] auf prefix_array[i-1] + arr[i].

• Innerhalb der Funktion int maximieren_sum(int prefix_array[], int size)

  • deklarieren Sie eine temporäre Variable temp und setzen Sie sie auf -1.

  • Beginnen Sie mit der Schleife von i bis 0, bis die Größe des Arrays erreicht ist. Setzen Sie innerhalb der Schleife temp auf max(temp, prefix_array[i])

  • Deklarieren Sie ein Array arr[temp +1] und initialisieren Sie alle Elemente des Arrays auf 0.

  • Beginnen Sie mit der Schleife von i bis 0, bis die Größe des Arrays erreicht ist. Deklarieren Sie innerhalb der Schleife eine temporäre Variable max_sum arr[prefix_array[i]]++

  • und setzen Sie sie auf 0. Deklarieren Sie eine Variable i als temp

  • , um die Schleife zu starten, wenn i>0. Überprüfen Sie, ob arr[i] > 0, dann setzen Sie max_sum auf max_sum + i und setzen Sie arr[i-1]-- und arr[i]--. Andernfalls dekrementieren Sie i um 1.

  • Max_sum zurückgeben.

Beispiel

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

Ausgabe

Wenn wir den obigen Code ausführen, wird die folgende Ausgabe generiert

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

Das obige ist der detaillierte Inhalt vonMaximieren Sie in C++ die Summe eines Arrays, indem Sie sein Präfix mit -1 multiplizieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!