Maximum Subarray (Максимальная сумма подмассива)
Описание: Дан массив целых чисел nums. Найдите непрерывный подмассив с наибольшей суммой и верните эту сумму. Подмассив должен содержать хотя бы один элемент.
Пример 1:
Вход: nums = [-2,1,-3,4,-1,2,1,-5,4]
Выход: 6
Объяснение: Подмассив [4,-1,2,1] даёт сумму 6
Пример 2:
Вход: nums = [-3,-1,-5]
Выход: -1
Объяснение: Все числа отрицательны, берём наибольшее
Ограничения:
1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
Рекомендуемая временная и пространственная сложность
Стремитесь к решению за O(n) по времени и O(1) по памяти.
Подсказка 1
Перебор всех подмассивов даёт O(n²). Можно ли пройти массив один раз?
Подсказка 2
Идите слева направо и храните лучшую сумму, заканчивающуюся в текущей позиции.
Подсказка 3
На каждом шаге выбор простой: продолжить предыдущий подмассив или начать новый с текущего элемента. Берите максимум из двух вариантов.