Задачка: Непрерывный подмассив
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Задачка: Непрерывный подмассив - 2008-09-30 14:08:37.080000
|
|
|
motorola
Сообщений: 64
Оценки: 0
Присоединился: 2007-11-13 19:44:42.273333
|
Вот задачк. Допустим, у вас есть массив целых чисел, как положительных, так и отрицательных, в произвольном порядке.
Найдите наибольшую возможную сумму любого сплошного подмассива.
Например, если все числа положительные, то наибольшей суммой будет сумма всех элементов массива; если все отрицательные — наибольшей суммой будет 0 (пустой подмассив)
Вот например массив чисел 1 2 3 -4 5, Я так понимаю. алгоритм должен складывать только положительные числа, или только сумма до -4?
|
|
|
|
|
RE: Задачка: Непрерывный подмассив - 2008-09-30 17:11:03.370000
|
|
|
_hel_
Сообщений: 103
Оценки: 0
Присоединился: 2008-07-09 16:00:40.600000
|
Если подумать, то да, считать надо только положительные, ведь надо найти наибольшую возможную сумму.
|
|
|
|
|
RE: Задачка: Непрерывный подмассив - 2008-09-30 21:55:38.613333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Если подумать, то нужно сделать именно то, что написано в задаче, а в задаче написано следующее:
quote:
Найдите наибольшую возможную сумму любого сплошного подмассива.
То есть, нужно проверить все возможные подмассивы и проверить сумму их элементов. Если мы берём массив [1, 2, 3, -4, 5], то сумма первых трёх элементов будет равна 6, сумма всего массива - 7, то есть сумма всего массива оказалась больше суммы первых трёх чисел. Но если бы последней была не пятерка, а, скажем, 3, то сумма была бы равна 5, то есть сумма всего массива оказалась уже меньше суммы подмассива.
А считать только положительные - это либо глупость, либо противоречит условиям задачи: нужно найти сумму сплошного подмассива, то есть отрицательные числа пропускать нельзя.
Вообще задача про два индекса - начальный и конечный. Прогоняем их в двух циклах for и проверяем сумму подмассивов между ними. Собственно всё.
|
|
|
|
|
RE: kreol - 2008-10-02 07:19:46.460000
|
|
|
motorola
Сообщений: 64
Оценки: 0
Присоединился: 2007-11-13 19:44:42.273333
|
Пасибо
|
|
|
|
|
|
