Вычисление максимальной суммы подряд идущих элементов массива

Задача:

• Дан некий массив числе, в котором есть как положительные, так и отрицательные числа
  • Нужно найти максимальную сумму, состоящую из элементов, идущих подряд

Решение:

• Сумму подмассива для первого элемента считаем как сумму самого себя
• Сумму следующего элемента вычисляем так:
  • Если сумма текущего элемента, с суммой прошлого подмассива больше значения текущего элемента - складываем текущий элемент с суммой элементов прошлого подмассива
  • Иначе наибольшей суммой данного подмассива считаем значение самого элемента

Сложность алгоритма - $O(n)$