|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Politov 2:5015/176.18 03 Mar 2002 07:16:48
To : Ilya Sergeev
Subject : Re: поиск подмассива с максимальной суммой элементов
--------------------------------------------------------------------------------
До меня дошли слухи, что *02.03.02* *12:35:41* пролетало сообщение
от Ilya к *All* про *"поиск подмассива с максимальной суммой элементов"*. И я
решил вмешаться.
U> Есть одномерный массив чисел. Hадо найти последовательность (начальный и
U> конечный индексы) элементов дающих максимальную сумму элементов среди
U> всех других последовательностей.
[...]
Просто перебираешь начало и конец этой последовательности, и ищешь
среди них с максимальной суммой. Если саму сумму считать по умному
то решение будет за O(n^2), по умному это так (я не утверждаю что
это наилучший способ, просто он сокращает время работы с O(n^3) до O(n^2)):
Заводим дополнительную переменную, в которой будем хранить текущую
сумму. Когда мы выбираем новое начало для нашей последовательности, то
значение этой переменной в 0, далее когда мы начинаем рассматривать
новый конец последовательности, то увеличиваем значение этой переменной
на значение элемена, который мы добавили к последовательности.
Реализация может выглядеть так:
b:= a[1]; ib:= 1; jb:= 1;
for i:= 1 to n do
begin
c:= 0;
for j:= i to n do
begin
inc(c,a[j]);
if c>b then
begin
b:= c;
ib:= i;
jb:= j;
end;
end;
end;
искомые индексы в ib,jb.
Искренне Ваш
Sergey Politov
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: Хороший гопник - мертвый гопник. (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: поиск подмассива с максимальной суммой элементов 
