|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serg Belyaev 2:5020/400 04 Mar 2002 19:33:05
To : Sergey Politov
Subject : Re: поиск подмассива с максимальной суммой элементов
--------------------------------------------------------------------------------
Привет!
U> Есть одномерный массив чисел. Hадо найти последовательность (начальный и
U> конечный индексы) элементов дающих максимальную сумму элементов среди
U> всех других последовательностей.
...
SP> то решение будет за O(n^2), по умному это так (я не утверждаю что
SP> это наилучший способ, просто он сокращает время работы с O(n^3) до
O(n^2)):
Олег Полубасов уже заметил:
OP> Грубовато. Hадо использовать динамическое программирование, тогда
OP> решение находится за O(n).
Я просто хочу немного добавить.
Эта классическая задача приведена в книге Ж.Арсака "Программирование
игр и головоломок" (головоломка 39. Другая головоломка Давида Грисса).
Очень рекомендую решать ее самостоятельно - испытаете истинное
удовлетворение. И из пушек по воробьям не стреляйте :)
Hиже приведен вариант решения (для сравнения с вашим)
9
8
7
6
5
4
3
2
1
0
var x :array[1..n] of integer;
smax,i,j :integer; { параметры найденного отрезка }
ii :integer; { индекс текущего начала }
s,k :integer; { текущая величина s-min и индекс }
begin
<ввод исходных данных>
smax:=x[1];i:=1;j:=1;
ii:=1;s:=0;
for k:=1 to n do begin
s:=s+x[k];
if s>smax then begin smax:=s;i:=ii;j:=k end;
if s<0 then begin s:=0;ii:=k+1 end;
end;
<вывод результата>
end.
--
<SVB>
--- ifmail v.2.15dev5
* Origin: Gamma NNTP server Moscow Russia (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
