Головоломка для программистов

[vak]

Задача из ru_programming: в заданном массиве целых чисел найти (непустой) отрезок с максимальной суммой. Массив разрешается просматривать всего один раз. Дополнительную память (массивы) использовать нельзя.

Нетерпеливые могут посмотреть решение здесь.

Comments

[dz.livejournal.com]

ну - три переменных-то можно? в одной храним текущую сумму - на каждом сдвиге окна приплюсовываем входящее значение и вычитаем "покинутое". ещё пара - чтобы хранить известный максимум и номер позиции, с которой начинается его окно.

[tnt23.livejournal.com]

Вот требование не использовать память меня подкосило - а как без переменных указать хотя бы начало и конец отрезка, я не очень представляю.

[vak]

Переменные можно. Нельзя требовать дополнительную память, пропорциональную длине входного массива.

[v1adis1av.livejournal.com]

А в сам массив писать можно? или он read-only?

[vak]

Нет, писать его не разрешается. Можно считать, что никаких массивов нет, а входные данные поступают последовательно по одному.

[vak]

Переменные можно. Но так просто не получается, попробуй. :)
Чтобы вычитать покинутое, придётся крутить цикл в цикле и иметь массив сумм для всех длин отрезков от 1 до N.

[dz.livejournal.com]

а, понял - нужно найти отрезок произвольной длины...