13: Maximum subarray

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

 

Пример 1

Input: [-4, 1, 2, -3, 1]
Output: 3

Пояснение: [1, 2] подмассив с максимальной суммой элементов равной 3

Пример 2

Input: [1, 1, 2, 5]
Output: 9