Задача эта появляется при распознавании одномерного шаблона; к ее истории мы обратимся позже. На входе имеется массив х из п вещественных чисел, на выходе должна быть получена максимальная сумма любой непрерывной последовательности элементов массива. Например, если во входном массиве содержатся следующие 10 элементов (рис. 8.1):
Рис. 8.1. Пример входного массива из 10 элементов
программа должна вернуть сумму х[2. .6], то есть 187. Задачу легко решить с положительными числами — максимальная сумма будет равна сумме всех элементов массива. Проблема возникает, когда появляются отрицательные числа: стоит ли включать такой элемент в выбранную последовательность, надеясь, что соседние компенсируют его? Чтобы завершить постановку задачи, скажем, что когда все элементы массива отрицательны, на выходе должна быть сумма элементов пустой последовательности элементов массива, равная нулю.
Первый вариант программы, который приходит в голову, перебирает все пары целых i и j, где 0<=i<=j<n; для каждой пары чисел вычисляется сумма x[i..j], после чего проверяется, превосходит ли она предыдущее найденное максимальное значение. Псевдокод алгоритма 1 приведен в листинге 8.1.
Опубликовал vovan666
April 17 2013 00:00:22 ·
0 Комментариев ·
3794 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
