Heim  >  Artikel  >  Backend-Entwicklung  >  Ich bin die große Matrix

Ich bin die große Matrix

Susan Sarandon
Susan SarandonOriginal
2024-11-24 12:13:14296Durchsuche

1975. Maximale Matrixsumme

Schwierigkeit:Mittel

Themen:Array, Greedy, Matrix

Sie erhalten eine n x n-Ganzzahlmatrix. Sie können den folgenden Vorgang beliebig oft ausführen:

  • Wählen Sie zwei beliebige benachbarte Elemente der Matrix und multiplizierenjedes davon mit -1.

Zwei Elemente gelten genau dann als benachbart, wenn sie eine Grenze teilen.

Ihr Ziel ist es, die Summe der Elemente der Matrix zu maximieren. Geben Sie die maximale Summe der Elemente der Matrix mithilfe der oben genannten Operation zurück.

Beispiel 1:

Maximum Matrix Sum

  • Eingabe:Matrix = [[1,-1],[-1,1]]
  • Ausgabe: 4
  • Erklärung: Wir können die folgenden Schritte ausführen, um die Summe gleich 4 zu erreichen:
    • Multiplizieren Sie die 2 Elemente in der ersten Zeile mit -1.
    • Multiplizieren Sie die 2 Elemente in der ersten Spalte mit -1.

Beispiel 2:

Maximum Matrix Sum

  • Eingabe: Matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
  • Ausgabe: 16
  • Erklärung: Wir können den folgenden Schritt befolgen, um die Summe gleich 16 zu erreichen:
    • Multiplizieren Sie die beiden letzten Elemente in der zweiten Zeile mit -1.

Einschränkungen:

  • n == matrix.length == matrix[i].length
  • 2 <= n <= 250
  • -105 <= Matrix[i][j] <= 105

Hinweis:

  1. Versuchen Sie, die Operation so zu verwenden, dass jede Zeile nur eine negative Zahl hat.
  2. Wenn Sie nur ein negatives Element haben, können Sie es nicht in ein positives umwandeln.

Lösung:

Um die Summe der Matrix mithilfe der Operation zu maximieren, müssen wir den absoluten Wert der negativen Beiträge zur Summe minimieren. Hier ist der Plan:

  1. Negative Zahlen zählen: Verfolgen Sie, wie viele negative Zahlen in der Matrix vorhanden sind.
  2. Mindestabsolutwert ermitteln:Bestimmen Sie den kleinsten Absolutwert in der Matrix, was hilfreich ist, wenn die Anzahl der Negative ungerade ist.
  3. Anpassen für ungerade Negative: Wenn die Anzahl der negativen Zahlen ungerade ist, kann der kleinste Absolutwert nicht ins Positive umgedreht werden, und dies begrenzt die maximal mögliche Summe.

Lassen Sie uns diese Lösung in PHP implementieren: 1975. Maximale Matrixsumme






Erläuterung:

  1. Summierung der absoluten Werte: Berechnen Sie die Summe der absoluten Werte aller Elemente, da die optimale Konfiguration so viele negative Zahlen wie möglich in positive umwandelt.
  2. Kleinsten Absolutwert verfolgen: Verwenden Sie dies, um die Summe anzupassen, wenn die Anzahl der negativen Zahlen ungerade ist.
  3. Behandeln Sie ungerade Negative:Subtrahieren Sie das Doppelte des kleinsten absoluten Werts von der Summe, um das unvermeidbare negative Element zu berücksichtigen, wenn die Negative nicht vollständig neutralisiert werden können.

Komplexität

  • Zeitliche Komplexität: O(n^2), da die Matrix einmal durchlaufen wird.
  • Raumkomplexität: O(1), da außer Variablen kein zusätzlicher Raum verwendet wird.

Diese Lösung arbeitet effizient innerhalb der gegebenen Einschränkungen.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

  • LinkedIn
  • GitHub

Das obige ist der detaillierte Inhalt vonIch bin die große Matrix. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
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