Maximum Subarray

Ein Teilarray ist eine zusammenhängende Folge benachbarter Elemente einer Liste, ohne Lücken. Unter allen nicht leeren Teilarrays einer Liste von Ganzzahlen möchtest du dasjenige finden, dessen Elemente sich zur größten Summe addieren, und diese Summe zurückgeben.

In [2, -4, 3, -1, 5, -6, 1] ist die beste Folge [3, -1, 5] mit einer Summe von 7. Sie enthält die -1, weil die darauffolgende 5 den Verlust mehr als ausgleicht, und lässt die 2 am Anfang aus, weil die darauffolgende -4 mehr kostet, als die 2 einbringt.

Die klassische Lösung in einem Durchlauf ist Kadanes Algorithmus. Gehe die Liste durch und behalte die beste Summe einer Folge, die beim aktuellen Element endet. Bei jedem Element gibt es nur zwei Möglichkeiten: Die Folge, die beim vorherigen Element endete, verlängern oder mit einer neuen Folge, die hier beginnt, neu starten. Das Verlängern lohnt sich nur, solange die vorherige Folge eine positive Summe hat; sobald diese Summe auf null oder darunter sinkt, kann es nur schaden, sie mitzunehmen, also beginnst du von vorn. Die Antwort ist die größte Summe einer Folge, die du unterwegs gesehen hast.

Im Beispiel lauten die besten Summen der Folgen, die an jeder Position enden, 2, -2, 3, 2, 7, 1 und 2; die Antwort ist also 7. Jedes Element wird einmal betrachtet, daher wächst der Aufwand linear mit der Länge der Liste.

Schreibe eine Funktion namens maxSubArray, die eine Liste von Ganzzahlen nums erhält und die größte Summe eines zusammenhängenden, nicht leeren Teilarrays von nums zurückgibt.

Einschränkungen: 1 ≤ nums.length ≤ 10^5, -10^4 ≤ nums[i] ≤ 10^4.