Дан непустой слайс целых чисел. Найдите непрерывный подмассив (хотя бы из
одного элемента) с наибольшей суммой и верните эту сумму.
// MaxSubArray возвращает наибольшую сумму непустого непрерывного подмассива.
func MaxSubArray(nums []int) int
Примеры
[-6, 3, -9, 12, -3, 6, 3, -15, 12] → 18 (подмассив [12, -3, 6, 3])
[-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6 ([4, -1, 2, 1])
[-3, -1, -2] → -1 (все отрицательные: берём один элемент)
[5] → 5
Ограничения
1 ≤ len(nums) ≤ 10⁶, |nums[i]| ≤ 10⁹ (сумма помещается в int64, но не
в int32).- Слайс менять нельзя.
- Ожидается O(n) по времени и O(1) памяти. Перебор всех подмассивов —
O(n²) — не уложится.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.