Подмассив с максимальной суммой
Дан массив из n целых чисел. Нужно найти непрерывный подмассив, сумма значений в котором будет наибольшей.
Входные данные
В первой строке вводится целое число n — количество элементов в массиве (1 ≤ n ≤ ).
Во второй строке вводятся n целых чисел, разделённых пробелом, которые являются элементами массива .
Выходные данные
Программа должна вывести одно целое число — наибольшую сумму элементов среди всех подмассивов данного массива.
Примеры
Входные данные | Выходные данные |
|---|---|
9 | 7 |
10 | 12 |
Пояснение
-2 1 -3
4 -1 3 1-4 -2 → сумма выделенного подмассива: (4 - 1 + 3 + 1) = 71 -2
3 4 -3 1 7-10 -20 4 → 3 + 4 -3 + 1 + 7 = 12
Можно ли улучшить это ещё больше 😎?
Решить эту задачу можно без использования дополнительных массивов. Справитесь?
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB