Maximum Subarray

Podtablica to ciąg sąsiadujących elementów listy, bez żadnych przerw. Spośród wszystkich niepustych podtablic listy liczb całkowitych znajdź tę, której elementy dają największą sumę, i zwróć tę sumę.

W [2, -4, 3, -1, 5, -6, 1] najlepszy ciąg to [3, -1, 5], którego suma wynosi 7. Zawiera on -1, ponieważ następująca po nim 5 z nawiązką rekompensuje jego wartość, a pomija początkowe 2, ponieważ następujące po nim -4 kosztuje więcej, niż daje 2.

Klasycznym rozwiązaniem wykonującym jedno przejście jest algorytm Kadane’a. Przejdź przez listę i przechowuj największą sumę ciągu kończącego się na bieżącym elemencie. Dla każdego elementu masz tylko dwie możliwości: rozszerzyć ciąg kończący się na poprzednim elemencie albo rozpocząć od nowa ciąg zaczynający się tutaj. Rozszerzanie się opłaca tylko wtedy, gdy wcześniejszy ciąg ma dodatnią sumę; gdy tylko suma spadnie do zera lub poniżej, dalsze jej uwzględnianie może jedynie zaszkodzić, więc zaczynasz od nowa. Odpowiedzią jest największa suma ciągu napotkana po drodze.

W tym przykładzie największe sumy ciągów kończących się na kolejnych pozycjach to 2, -2, 3, 2, 7, 1 i 2, więc odpowiedź wynosi 7. Każdy element jest sprawdzany raz, dlatego nakład pracy rośnie liniowo wraz z długością listy.

Napisz funkcję o nazwie maxSubArray, która otrzymuje listę liczb całkowitych nums i zwraca największą sumę spójnej, niepustej podtablicy nums.

Ograniczenia: 1 ≤ nums.length ≤ 10^5, -10^4 ≤ nums[i] ≤ 10^4.