Inhaltsverzeichnis
Das Präfix-Array wird wie folgt generiert:
Die im folgenden Programm verwendete Methode lautet wie folgt: -
Beispiel
Ausgabe
Heim Backend-Entwicklung C++ Maximieren Sie in C++ die Summe eines Arrays, indem Sie sein Präfix mit -1 multiplizieren

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

Sep 08, 2023 pm 03:17 PM
c编程 Array-Summe Präfixoperation

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;
}
Nach dem Login kopieren

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
Nach dem Login kopieren

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!

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Beste grafische Einstellungen
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. So reparieren Sie Audio, wenn Sie niemanden hören können
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25: Wie man alles in Myrise freischaltet
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Verwenden Sie C++, um Code zu schreiben, um die N-te nichtquadratische Zahl zu finden Verwenden Sie C++, um Code zu schreiben, um die N-te nichtquadratische Zahl zu finden Aug 30, 2023 pm 10:41 PM

Wir alle kennen Zahlen, die nicht das Quadrat einer Zahl sind, wie zum Beispiel 2, 3, 5, 7, 8 usw. Es gibt N nichtquadratische Zahlen und es ist unmöglich, jede Zahl zu kennen. In diesem Artikel erklären wir alles über quadratlose oder nichtquadratische Zahlen und Möglichkeiten, die N-te nichtquadratische Zahl in C++ zu finden. N-te nichtquadratische Zahl Wenn eine Zahl das Quadrat einer ganzen Zahl ist, wird die Zahl als perfektes Quadrat bezeichnet. Einige Beispiele für perfekte Quadratzahlen sind -1isquadratvon14isquadratvon29isquadratvon316isquadratvon425isquadratvon5. Wenn eine Zahl nicht das Quadrat einer ganzen Zahl ist, wird die Zahl als nichtquadratisch bezeichnet. Die ersten 15 nichtquadratischen Zahlen sind beispielsweise -2,3,5,6,

Inversionsalgorithmus für die Rechtsdrehung eines Arrays, geschrieben in C++ Inversionsalgorithmus für die Rechtsdrehung eines Arrays, geschrieben in C++ Sep 08, 2023 pm 08:17 PM

In diesem Artikel lernen wir den Umkehralgorithmus kennen, um das gegebene Array um k Elemente nach rechts zu drehen, zum Beispiel −Input:arr[]={4,6,2,6,43,7,3,7}, k= 4Ausgabe:{43,7,3,7,4,6,2,6}Erklärung:Das Drehen jedes Elements des Arrays um 4 Elemente nach rechts ergibt {43,7,3,7,4,6,2,6}.Eingabe:arr[]= {8 ,5,8,2,1,4,9,3},k=3Ausgabe:{4,9,3,8,5,8,2,1} Finden Sie die Lösung

Ermitteln Sie in der C-Programmierung die Fläche eines Kreises Ermitteln Sie in der C-Programmierung die Fläche eines Kreises Aug 25, 2023 pm 10:57 PM

Ein Kreis ist eine geschlossene Figur. Alle Punkte auf einem Kreis haben den gleichen Abstand von einem Punkt innerhalb des Kreises. Der Mittelpunkt wird Kreismittelpunkt genannt. Der Abstand von einem Punkt zum Mittelpunkt eines Kreises wird Radius genannt. Die Fläche ist eine quantitative Darstellung der Dimensionsspanne einer geschlossenen Figur. Die Fläche eines Kreises ist die Fläche, die innerhalb der Abmessungen des Kreises eingeschlossen ist. Die Formel zur Berechnung der Fläche eines Kreises lautet Fläche=π*r*r. Um die Fläche zu berechnen, geben wir den Radius des Kreises als Eingabe ein. Wir verwenden die Formel zur Berechnung der Fläche, Algorithmus SCHRITT 1: Übernehmen Sie den Radius als Eingabe vom Benutzer mit stdin. SCHRITT 2 : Berechnen Sie die Fläche des Kreises mit Fläche=(

Ermitteln Sie mit C++ die Anzahl eindeutiger Paare in einem Array Ermitteln Sie mit C++ die Anzahl eindeutiger Paare in einem Array Sep 07, 2023 am 11:53 AM

Wir benötigen entsprechende Kenntnisse, um mehrere eindeutige Paare in der Array-Syntax von C++ zu erstellen. Während wir die Anzahl der eindeutigen Paare ermitteln, zählen wir alle eindeutigen Paare im angegebenen Array, d. h. alle möglichen Paare können gebildet werden, wobei jedes Paar eindeutig sein sollte. Zum Beispiel -Input:array[]={5,5,9}Output:4Erläuterung:Die Anzahl dereinzigartigen Paaresind(5,5),(5,9),(9,5)und(9,9).Input:array[] = {5,4,3,2,2}Ausgabe: 16 Möglichkeiten, eine Lösung zu finden Es gibt zwei Möglichkeiten, dieses Problem zu lösen: −

Schreiben Sie mit C++ einen Code, um die Anzahl der Subarrays mit denselben Mindest- und Höchstwerten zu ermitteln Schreiben Sie mit C++ einen Code, um die Anzahl der Subarrays mit denselben Mindest- und Höchstwerten zu ermitteln Aug 25, 2023 pm 11:33 PM

In diesem Artikel werden wir C++ verwenden, um das Problem zu lösen, die Anzahl der Subarrays zu ermitteln, deren Maximal- und Minimalwert gleich sind. Das Folgende ist ein Beispiel für das Problem: −Input:array={2,3,6,6,2,4,4,4}Output:12Explanation:{2},{3},{6},{6}, {2 },{4},{4},{4},{6,6},{4,4},{4,4}und {4,4,4}sind die Teilarrays, die mit dem gleichen maximalen und minimalen Element gebildet werden können. Eingabe: array={3, 3, 1,5,

Kehren Sie die Gruppierung doppelt verknüpfter Listen nach gegebener Größe mit C++ um Kehren Sie die Gruppierung doppelt verknüpfter Listen nach gegebener Größe mit C++ um Sep 04, 2023 am 09:49 AM

In diesem Problem erhalten wir einen Zeiger auf den Kopf der verknüpften Liste und eine ganze Zahl k. In einer Gruppe der Größe k müssen wir die verknüpfte Liste umkehren. Zum Beispiel -Input:1<->2<->3<->4<->5(doublylinkedlist),k=3Output:3<->2<->1<->5<->4 sucht nach Lösungen Methode In diesem Problem werden wir einen rekursiven Algorithmus formulieren, um dieses Problem zu lösen. Bei dieser Methode verwenden wir die Rekursion und lösen das Problem mithilfe der Rekursion. Beispiel#include<iostream&

Ermitteln Sie in C++ die Anzahl der reflexiven Beziehungen auf einer Menge Ermitteln Sie in C++ die Anzahl der reflexiven Beziehungen auf einer Menge Aug 26, 2023 pm 08:17 PM

In diesem Artikel erklären wir Möglichkeiten, reflexive Beziehungen auf einer Menge zu finden. In diesem Problem erhalten wir eine Zahl n und eine Menge von n natürlichen Zahlen und müssen die Anzahl der reflexiven Beziehungen bestimmen. Reflexive Relation – Eine Relation R heißt eine reflexive Relation auf der Menge A, wenn für jedes „a“ in der Menge A (a, a) zur Relation R gehört. Zum Beispiel -Input:x=1Output:1Explanation:set={1},reflexiverelationsonA*A:{{1}}Input:x=2Output:4Explanation:set={1,2},reflexiverelationsonA*

Umkehralgorithmus für die Array-Rotation, geschrieben in C++ Umkehralgorithmus für die Array-Rotation, geschrieben in C++ Aug 28, 2023 pm 11:13 PM

In dem gegebenen Problem haben wir ein Array und müssen das Array mit einem Inversionsalgorithmus wie −Input:arr[]=[1,2,3,4,5,6,7], d=2Output um d Elemente drehen: arr[]=[3,4,5,6,7,1,2]Erklärung: Wie Sie sehen können, müssen wir dieses Array um d=2 drehen, aber unsere Hauptaufgabe besteht darin, dies mithilfe einer Umkehrtechnik zu erreichen, und sind zu dem Schluss gekommen: Zuerst kehren wir um

See all articles