Найти максимальный подмассив
Сложность: Средняя
Условие задачи: дан целочисленный массив, необходимо найти в нем такой подмассив, сумма элементов в котором будет максимальной.
Подмассивом называется последовательная часть исходного массива.
Пример:
Ввод:
Вывод: 6
Объяснение:
Ввод:
Вывод: 23
Решение:
Пишите свое решение в комментариях👇
@python_job_interview
Сложность: Средняя
Условие задачи: дан целочисленный массив, необходимо найти в нем такой подмассив, сумма элементов в котором будет максимальной.
Подмассивом называется последовательная часть исходного массива.
Пример:
Ввод:
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