Найти максимальный подмассив

Сложность: Средняя

Условие задачи: дан целочисленный массив, необходимо найти в нем такой подмассив, сумма элементов в котором будет максимальной.

Подмассивом называется последовательная часть исходного массива.

Пример:

Ввод: nums = [-2,1,-3,4,-1,2,1,-5,4]
Вывод: 6

Объяснение: 4,-1,2,1] имеет наибольшую сумму 6.

Ввод: nums = [5,4,-1,7,8]
Вывод: 23

Решение:

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
Max = nums[0]
Sum = 0
for num in nums:
Sum += num
Max = max(Max, Sum)
if Sum<0:
Sum = 0
return Max

Пишите свое решение в комментариях👇

@python_job_interview