Алгоритм

← →
Din (2005-12-18 20:30) [0]

всем добрый вечер
есть такая задача:

дан некоторый массив чисел (числа могут быть как положительными так и отрицательными)
необходимо следующее: найти максимальный подвектор массива
Подвектор - один или более(сумма ) элементов массива
Нужен алгоритм с минимальной сложностью
я на асме написал со сложностью N^2 , а надо хотя бы Log(N)
Подскажите как.(код программы не надо только принцип)

← →
palva © (2005-12-18 20:47) [1]

Просматриваем все элементы и складываем положительные. Это, конечно, не Log(N), но хотя бы линейная сложность.

← →
Din (2005-12-18 20:51) [2]

учитывая что подвектор включает в себя элементы массива ПО ПОРЯДКУ а элементы положительные/отрицательные равновероятны то выигрыш не о4 большой, если массив генератором получен то там почти через один будут идти +/-

← →
Din (2005-12-18 21:06) [3]

например

85 32
-1 -28
72 12
-2 или -80
48 40
-11 -76

тут надо и отрицательные проверять
может еще кто какой способ подскажет

← →
TUser © (2005-12-18 21:13) [4]

> найти максимальный подвектор массива
> Подвектор - один или более(сумма ) элементов массива

Результат - это просто сумма положительных элементов. За лог N - фиг сделаешь, каждый элемент хотя бы раз надо посмотреть.

← →
Din (2005-12-18 21:17) [5]

я может неточно выразился ПОДВЕКТОР - сумма последовательных элементов массива

← →
TUser © (2005-12-18 21:23) [6]

Аааа. Ну так бы и сказанул. Задача решается динамиским программированием за линейное время. Храни информацию о двух подвекторах - самом распрекрасном из найденных до сих пор, и самом лучшем из заканчивающихся в текущей позиции. Просматриваешь весь массив, - и получаешь нужный результат.

← →
Din (2005-12-18 21:26) [7]

я просто думал что если подвектор то как бы само последовательные)

← →
TUser © (2005-12-18 21:28) [8]

Ну, это ты так думал. А мы вольны прочитать

> Подвектор - один или более(сумма ) элементов массива

и сообразить, что надобно просто просуммировать положительные элементы, что и сказано в [1].

← →
Din (2005-12-18 21:30) [9]

тока я не совсем понял что ты имел ввиду ведь тады мы все равно весь массив просматриваем или нет?

← →
Din (2005-12-18 21:32) [10]

если тока положительные проблем бы не было, какие там сложности)))

У тебя есть число n. Оно бежит от 1 до длины массива. На каждом шаге есть а. начало и конец наибольшей (с всмысле определенной меры) цепочки, такие, что и начало, и конец - меньше либо равны текущему значению n.
б. начало наибольшей (...) цепочки, заканчивающейся в текущей позиции.

Вывбирай наибольшеее. Или я чего-то не понял?

Алгоритм Найти похожие ветки