10,3 тыс подписчиков
Найти максимальный подмассив
Сложность: Средняя
Условие задачи: дан целочисленный массив, необходимо найти в нем такой подмассив, сумма элементов в котором будет максимальной.
Подмассивом называется последовательная часть исходного массива.
Пример:
Ввод: 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
Пишите свое решение в комментариях👇
Около минуты
18 июня 2023
217 читали