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

[vak]

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

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

Comments

[spamsink]

Эта задача - чуть ли не единственное, что я помню из занятий по программированию в Керосинке. Очень понравилось в свое время.

если разрешать отрезки нулевой длины

[a-shen.livejournal.com]

k:=0; lastmax:=0; totalmax:=0;
{lastmax=максимальная сумма по отрезкам, примыкающим к концу a[1..k], totalmax=максимальная сумма по всем отрезкам}
while (k not equal to n) do begin
k:=k+1;
lastmax:=max(lastmax+a[k],0);
totalmax:=max(lastmax,totalmax);
end;

[vak]

Требуется сам отрезок, а не его сумма. Отрезки нулевой длины тоже нехорошо.

ну тогда

[a-shen.livejournal.com]

k:=1;
lastmax:=(a[1],1,1);
totalmax:=lastmax;
{last,totalmax = (value, first, last)
for maximal sums at the end and in total}
while (k not equal to n) do begin
k:=k+1;
if lastmax.1 less than 0 then begin
lastmax.1:=a[k];
lastmax.2:=k;
lastmax.3:=k;
end else begin
lastmax.1 := lastmax.1+a[k];
lastmax.3 := k;
end;
if lastmax.1 GT totalmax.1 then begin
totalmax:=lastmax;
end;
end;

[dz.livejournal.com]

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

[tnt23.livejournal.com]

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

[vak]

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

[v1adis1av.livejournal.com]

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

[vak]

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

[vak]

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

[dz.livejournal.com]

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

[tnt23.livejournal.com]

Дык отрезок длиной в сам массив и будет искомым :) или числа в массиве могут быть отрицательными?

[vak]

Могут быть отрицательными, конечно.

[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]

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