. Maximale Summe überlappender Subarrays

689. Maximale Summe von 3 nicht überlappenden Subarrays

Schwierigkeit:Schwer

Themen:Array, dynamische Programmierung

Suchen Sie bei einem gegebenen ganzzahligen Array nums und einer ganzen Zahl k drei nicht überlappende Unterarrays der Länge k mit maximaler Summe und geben Sie sie zurück.

Gib das Ergebnis als Liste von Indizes zurück, die die Startposition jedes Intervalls darstellen (0-indexiert). Wenn es mehrere Antworten gibt, geben Sie die lexikografisch kleinste Antwort zurück.

Beispiel 1:

• Eingabe: nums = [1,2,1,2,6,7,5,1], k = 2
• Ausgabe: [0,3,5]
• Erklärung: Subarrays [1, 2], [2, 6], [7, 5] entsprechen den Startindizes [0, 3, 5].
  • Wir hätten auch [2, 1] nehmen können, aber eine Antwort von [1, 3, 5] wäre lexikografisch umfangreicher.

Beispiel 2:

• Eingabe: nums = [1,2,1,2,1,2,1,2,1], k = 2
• Ausgabe: [0,2,4]

Einschränkungen:

• 1 <= nums.length <= 2 * 10⁴
• 1 <= nums[i] < 2¹⁶
• 1 <= k <= floor(nums.length / 3)

Lösung:

Wir werden einen dynamischen Programmieransatz verwenden. Die Idee besteht darin, das Problem in kleinere Teilprobleme zu zerlegen und dabei die Überlappung von Teilarrays zu nutzen, um die maximale Summe von drei nicht überlappenden Teilarrays der Länge k effizient zu berechnen.

Ansatz:

1. Berechnen Sie die Summen von Unterarrays der Länge k vor:
   Zuerst berechnen wir die Summe aller Subarrays der Länge k im Eingabearray nums. Dies kann mithilfe einer Schiebefenstertechnik effizient in linearer Zeit erfolgen.

2. Dynamische Programmierung (DP):
   Wir erstellen zwei Hilfsarrays, links und rechts, um die Indizes der besten gefundenen Subarrays bis zur aktuellen Position zu speichern. Das linke[i] speichert den Index des besten Subarrays, das vor dem Index i endet, und das rechte[i] speichert den Index des besten Subarrays, das nach dem Index i beginnt.

3. Iterieren und berechnen Sie die maximale Summe:
   Für jedes mögliche mittlere Subarray ab Index j berechnen wir die Gesamtsumme, indem wir das beste linke Subarray vor j und das beste rechte Subarray nach j berücksichtigen.

4. Lexikografische Reihenfolge:
   Bei mehreren gültigen Antworten (mit gleicher Summe) geben wir die lexikografisch kleinste Antwort zurück. Dies wird durch die Reihenfolge der Iteration sichergestellt.

Lassen Sie uns diese Lösung in PHP implementieren: 689. Maximale Summe von 3 nicht überlappenden Subarrays

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer[]
 */
function maxSumOfThreeSubarrays($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
print_r(maxSumOfThreeSubarrays([1,2,1,2,6,7,5,1], 2)); // [0, 3, 5]
print_r(maxSumOfThreeSubarrays([1,2,1,2,1,2,1,2,1], 2)); // [0, 2, 4]
?>




<h3>
  
  
  Erläuterung:
</h3>

<ol>
<li>
<p><strong>Berechnung der Subarray-Summen:</strong></p>

<ul>
<li>Wir berechnen die Summe aller möglichen Subarrays der Länge k. Dazu wird zunächst die Summe der ersten k Elemente berechnet. Dann subtrahieren wir für jede nachfolgende Position das verbleibende Element und fügen das nächste Element im Array hinzu, was es zu einem effizienten Schiebefenster-Ansatz macht.</li>
</ul>
</li>
<li>
<p><strong>Linke und rechte Arrays:</strong></p>

<ul>
<li>
left[i] enthält den Index des Subarrays mit der maximalen Summe, die vor Index i endet.</li>
<li>
right[i] enthält den Index des Subarrays mit der maximalen Summe, die nach Index i beginnt.</li>
</ul>
</li>
<li>
<p><strong>Endgültige Berechnung:</strong></p>

<ul>
<li>Für jedes mittlere Subarray j prüfen wir die Kombination des besten linken Subarrays und des besten rechten Subarrays und aktualisieren das Ergebnis, wenn die Summe größer als das aktuelle Maximum ist.</li>
</ul>
</li>
<li>
<p><strong>Lexikografisch kleinste Antwort:</strong></p>

<ul>
<li>Während wir von links nach rechts iterieren, stellen wir die lexikografisch kleinste Lösung sicher, indem wir auf natürliche Weise die ersten Unterarrays auswählen, die die maximale Summe ergeben.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Beispiel:
</h3>

<p>Zur Eingabe:<br>
</p>

<pre class="brush:php;toolbar:false">$nums = [1, 2, 1, 2, 6, 7, 5, 1];
$k = 2;

Die Ausgabe wird sein:

[0, 3, 5]

Dieser Ansatz stellt sicher, dass die Zeitkomplexität effizient bleibt, mit einer Zeitkomplexität von ungefähr O(n), wobei n die Länge der Eingabearray-Zahlen ist.

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 von. Maximale Summe überlappender Subarrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!