Maximum Subarray

Подмассив — это последовательность соседних элементов списка без пропусков. Среди всех непустых подмассивов списка целых чисел нужно найти тот, сумма элементов которого максимальна, и вернуть эту сумму.

В [2, -4, 3, -1, 5, -6, 1] лучшая последовательность — [3, -1, 5], сумма которой равна 7. В неё входит -1, потому что следующее за ним число 5 с лихвой компенсирует его, а начальное число 2 не входит, потому что следующее за ним -4 отнимает больше, чем даёт 2.

Классическое решение за один проход — алгоритм Кадане. Проходите по списку и храните наибольшую сумму последовательности, заканчивающейся на текущем элементе. Для каждого элемента есть всего два варианта: продлить последовательность, заканчивавшуюся на предыдущем элементе, или начать заново новую последовательность с текущего элемента. Продлевать выгодно, только пока сумма предыдущей последовательности положительна; как только она становится равной нулю или меньше, продолжение может только навредить, поэтому начинайте заново. Ответ — наибольшая сумма последовательности, встретившаяся за весь проход.

В этом примере наибольшие суммы последовательностей, заканчивающихся на каждой позиции, равны 2, -2, 3, 2, 7, 1 и 2, поэтому ответ — 7. Каждый элемент просматривается один раз, поэтому объём работы растёт линейно с длиной списка.

Напиши функцию с именем maxSubArray, которая получает список целых чисел nums и возвращает наибольшую сумму непрерывного непустого подмассива nums.

Ограничения: 1 ≤ nums.length ≤ 10^5, -10^4 ≤ nums[i] ≤ 10^4.