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

[vak]

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

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

Comments

[v1adis1av.livejournal.com]

Пусть S(i) -- сумма элементов массива от 0 до i. Тогда границами искомого отрезка будет слева -- точка i(Min), где достигается глобальный минимум функции S(i), справа -- точка i(Max) глобального максимума. Однако этот подход неприменим к случаю, когда глобальный минимум находится справа от гл.максимума. Так что задача сложнее, чем кажется на первый взгляд: нужно найти "почти глобальный" минимум i(min1) на всей области слева от глобального максимума i(Max) и "почти глобальный" максимум i(max1) на всей области справа от глобального минимума i(Min), затем сравнить Max-min1 и max1-Min. Тот из этих двух отрезков, для которого разность больше, и будет искомым (если гл.минимум слева от гл.максимума, то эти два отрезка суть один). Ессно, всё это можно сделать за один проход по массиву.

[vak]

Совершенно верно. И не забыть про случай, когда все элементы массива отрицательные.