Algorithmen und Datenstrukturen · Middle · Frage 47 von 75
Was ist die Idee von Kadanes Algorithmus für die maximale Teilarray-Summe?
- 1Das Array sortieren und alle positiven Zahlen addieren
- 2Die beste hier endende Summe führen: verlängern oder neu beginnen
- 3Die Summe jedes möglichen Teilarrays einmal prüfen
Antwort zeigen
Richtige Antwort: Die beste hier endende Summe führen: verlängern oder neu beginnen
Erklärung
cur = Math.max(x, cur + x), best = Math.max(best, cur). Eine negative laufende Summe schadet nur, also fällt sie weg. Ein Durchlauf, O(n), statt O(n²) für alle Teilarrays.