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

[vak]

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

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

Comments

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