Воспользуемся простейшим алгоритмом для работы с массивами. Начинать следует с левого конца массива (элемента х[0]), затем нужно перебрать все элементы и закончить на правом конце (элемент х[п-1]), все время сохраняя информацию о наилучшей на данный момент сумме. Изначально максимальная сумма равна нулю. Предположим, что мы решили задачу для х[0. .1-1], как можно расширить ее решение, добавив в него элемент x[i]? Используем те же соображения, что и для алгоритма «разделяй и властвуй»: подпоследовательность первых i элементов с максимальной суммой может либо целиком лежать в первых i элементах (хранится в maxsofar), либо заканчиваться элементом i (хранится в maxendinghere).
maxsofar maxendinghere
Вычисление maxendinghere каждый раз заново, аналогично алгоритму 3, даст нам в итоге еще один квадратичный алгоритм. Мы можем обойти это, используя тот же метод, который привел нас к алгоритму 2: вместо того, чтобы находить максимальную подпоследовательность, заканчивающуюся элементом i, мы воспользуемся максимальной подпоследовательностью, заканчивавшейся элементом i-1. В итоге получаем алгоритм 4 (листинг 8.5).
Листинг 8.5. Четвертый алгоритм решения задачи о максимальной подпоследовательности
maxsofar = О maxendinghere - О for i = [0, п)
/* инвариант: значения maxendinghere и maxsofar точны для x[Q..i-l] */ maxendinghere = max(maxendinghere + x[i], 0) maxsofar = max(maxsofar, maxendinghere)
Ключ к пониманию этой программы — переменная maxendinghere. Перед первым оператором присваивания в цикле значение переменной равно максимальной сумме подпоследовательностей, заканчивающихся элементом i-1. Оператор присваивания изменяет ее содержимое таким образом, что оно становится равным максимальной сумме подпоследовательностей, заканчивающихся элементом i. Оператор увеличивает это значение добавлением x[i] до тех пор, пока это действие оставляет сумму подпоследовательности положительной; возможные отрицательные значения заменяются нулем, поскольку максимальная по сумме подпоследовательность, заканчивающаяся элементом i, теперь является пустой. Хотя этот код труден для понимания, он прост и быстр, потому что выполняется за 0(п) операций. Такие алгоритмы называются линейными.
Опубликовал vovan666
April 17 2013 00:00:37 ·
0 Комментариев ·
4362 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
