Ich bin die große Matrix

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:

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

• 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
• -10⁵ <= Matrix[i][j] <= 10⁵

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:




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.

Kleinsten Absolutwert verfolgen: Verwenden Sie dies, um die Summe anzupassen, wenn die Anzahl der negativen Zahlen ungerade ist.

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!