В информатике , то максимальная сумма проблема подмассива является задачей нахождения смежного подмассива с наибольшей суммой, в пределах заданного одномерного массива A [1 ... п] числа. Формально задача найти индексы а также с участием , такая что сумма
как можно больше. (Некоторые формулировки задачи также позволяют рассматривать пустой подмассив; по соглашению сумма всех значений пустого подмассива равна нулю.) Каждое число во входном массиве A может быть положительным, отрицательным или нулевым. [1]
Например, для массива значений [−2, 1, −3, 4, −1, 2, 1, −5, 4] непрерывный подмассив с наибольшей суммой равен [4, −1, 2, 1] , с суммой 6.
Некоторые свойства этой проблемы:
- Если массив содержит все неотрицательные числа, проблема тривиальна; максимальный подмассив - это весь массив.
- Если массив содержит все неположительные числа, то решением является любой подмассив размером 1, содержащий максимальное значение массива (или пустой подмассив, если это разрешено).
- Несколько разных подмассивов могут иметь одинаковую максимальную сумму.
Эта проблема может быть решена с использованием нескольких различных алгоритмических методов, включая грубую силу, [2] разделяй и властвуй, [3] динамическое программирование [4] и сокращение до кратчайших путей. [ необходима цитата ]
История
Задача максимального подмассива была предложена Ульфом Гренандером в 1977 году как упрощенная модель для оценки максимального правдоподобия шаблонов в оцифрованных изображениях. [5]
Гренандер искал прямоугольный подмассив с максимальной суммой в двумерном массиве действительных чисел. Алгоритм грубой силы для двумерной задачи выполняется за время O ( n 6 ); поскольку это происходило слишком медленно, Гренандер предложил одномерную задачу, чтобы понять ее структуру. Гренандер разработал алгоритм, который решает одномерную задачу за время O ( n 2 ) [примечание 1], улучшая время работы грубой силы O ( n 3 ). Когда Майкл Шамос услышал о проблеме, он в одночасье разработал для нее алгоритм «разделяй и властвуй» за O ( n log n ) . Вскоре после этого Шамос описал одномерную проблему и ее историю на семинаре Университета Карнеги-Меллона, на котором присутствовал Джей Кадейн , который в течение минуты разработал алгоритм за время O ( n ), [5] [6] [7], который выглядит следующим образом: как можно быстрее. [примечание 2] В 1982 году Дэвид Грайс получил тот же алгоритм за время O ( n ), применяя «стандартную стратегию» Дейкстры ; [8] в 1989 году Ричард Берд вывел его путем чисто алгебраической манипуляции с алгоритмом грубой силы с использованием формализма Берда – Меертенса . [9]
Двумерное обобщение Гренандера может быть решено за время O ( n 3 ) либо с помощью алгоритма Кадана в качестве подпрограммы, либо с помощью подхода «разделяй и властвуй». Немного более быстрые алгоритмы, основанные на умножении матриц расстояний , были предложены Тамаки и Токуяма (1998) и Такаока (2002) . Есть некоторые свидетельства того, что не существует значительно более быстрого алгоритма; алгоритм, который решает двумерную задачу о максимуме подмассива за время O ( n 3 − ε ) для любого ε> 0, будет предполагать аналогичный быстрый алгоритм для задачи поиска кратчайших путей для всех пар . [10]
Приложения
Проблемы с максимальным подмассивом возникают во многих областях, таких как анализ геномной последовательности и компьютерное зрение .
Анализ геномной последовательности использует алгоритмы максимального подмассива для идентификации важных биологических сегментов белковых последовательностей. [ необходима цитата ] Эти проблемы включают консервативные сегменты, GC-богатые области, тандемные повторы, фильтр низкой сложности, ДНК-связывающие домены и области с высоким зарядом. [ необходима цитата ]
В компьютерном зрении алгоритмы максимального подмассива используются в растровых изображениях для обнаружения самой яркой области изображения.
Алгоритм Кадане
Пример запуска |
---|
Алгоритм Кадане сканирует данный массивслева направо. в-й шаг, он вычисляет подмассив с наибольшей суммой, заканчивающейся на ; эта сумма сохраняется в переменной current_sum
. [примечание 3] Кроме того, он вычисляет подмассив с наибольшей суммой в любом месте, поддерживается в переменной best_sum
, [примечание 4] и легко получается как максимум из всех значений, current_sum
замеченных до сих пор, ср. строка 7 алгоритма.
Как инвариант цикла , в-м шаге старое значение current_sum
удерживает максимум по всем суммы . [примечание 5] Следовательно,current_sum
[примечание 6] - это максимум по всем суммы . Чтобы расширить последний максимум, чтобы охватить также случай, достаточно рассмотреть также пустой подмассив . Это делается в строке 6 путем присвоенияcurrent_sum
как новое значение current_sum
, которое после этого удерживает максимум по всем суммы .
Таким образом, проблема может быть решена с помощью следующего кода [4] [7], выраженного здесь на Python :
def max_subarray ( числа ): "" "Найдите наибольшую сумму из любого непрерывного подмассива." "" best_sum = 0 # или: float ('- inf') current_sum = 0 для x в числах : текущая_сумма = макс ( 0 , текущая_сумма + х ) best_sum = макс ( best_sum , current_sum ) вернуть best_sum
Эта версия алгоритма вернет 0, если вход не содержит положительных элементов (в том числе, когда вход пуст). Для варианта проблемы, который запрещает пустые подмассивы, best_sum
вместо этого следует инициализировать отрицательную бесконечность [11], а также в цикле for current_sum
следует обновить как max(x, current_sum + x)
. [примечание 7] В этом случае, если входные данные не содержат положительного элемента, возвращаемое значение - это значение самого большого элемента (т. е. наименьшее отрицательное значение) или отрицательная бесконечность, если вход был пуст.
Алгоритм можно изменить, чтобы отслеживать начальный и конечный индексы максимального подмассива:
def max_subarray ( числа ): "" "Найдите непрерывный подмассив с наибольшей суммой." "" best_sum = 0 # или: float ('- inf') best_start = best_end = 0 # или: Нет current_sum = 0 для current_end , x в перечислении ( числа ): если текущая_сумма <= 0 : # Начать новую последовательность с текущего элемента current_start = current_end current_sum = x еще : # Расширить существующую последовательность текущим элементом текущая_сумма + = х если current_sum > best_sum : best_sum = current_sum best_start = current_start best_end = current_end + 1 # +1 делает исключительным 'best_end' вернуть best_sum , best_start , best_end
В Python массивы индексируются, начиная с 0, а конечный индекс обычно исключается, так что подмассив [22, 33] в массиве [-11, 22, 33, -44] будет начинаться с индекса 1 и заканчиваться индексом 3.
Поскольку в этом алгоритме используются оптимальные подструктуры (максимальный подмассив, заканчивающийся в каждой позиции, вычисляется простым способом из связанной, но меньшей и перекрывающейся подзадачи: максимальный подмассив, заканчивающийся в предыдущей позиции), этот алгоритм можно рассматривать как простой / тривиальный пример динамического программирования .
Сложность выполнения алгоритма Кадане составляет . [4] [7]
Обобщения
Подобные проблемы могут возникать и для многомерных массивов, но их решения более сложны; см., например, Такаока (2002) . Brodal & Jørgensen (2007) показали, как найти k наибольших сумм подмассива в одномерном массиве за оптимальное время..
Максимальная сумма k- непересекающихся подмассивов также может быть вычислена в оптимальном временном интервале.. [12]
Смотрите также
- Проблема суммы подмножества
Заметки
- ^ Используя предварительно вычисленную таблицу совокупных сумм для вычисления суммы подмассива в постоянное время
- ^ поскольку каждый алгоритм должен хотя бы один раз просканировать массив, что уже занимает время O ( n )
- ^ назван
MaxEndingHere
в Bentley (1989) , иc
в Gries (1982) - ^ назван
MaxSoFar
в Bentley (1989) , иs
в Gries (1982) - ^ Эта сумма равна когда , соответствующий пустому подмассиву .
- ^ В коде Pythonвыражается как
x
, с индексом слева неявно. - ^ Хотя последняя модификация не упоминается Бентли (1989) , она позволяет поддерживать измененный инвариант цикла.
current_sum
в начале -й шаг.
Рекомендации
- Перейти ↑ Bentley 1989 , p. 69.
- Перейти ↑ Bentley 1989 , p. 70.
- Перейти ↑ Bentley 1989 , p. 73.
- ↑ a b c Bentley 1989 , стр. 74.
- ^ a b Bentley 1984 , стр. 868-869.
- Перейти ↑ Bentley 1989 , p. 76-77.
- ^ a b c Грис 1982 , стр. 211.
- ^ Грис 1982 , с. 209-211.
- ^ Bird 1989 , Sect.8, с.126.
- ^ Backurs, Dikkala & Tzamos 2016 .
- Перейти ↑ Bentley 1989 , p. 78 171.
- Перейти ↑ Bengtsson & Chen 2007 .
- Бакурс, Артурс; Диккала, Нишант; Цамос, Христос (2016), «Результаты жесткой жесткости для прямоугольников с максимальным весом», Proc. 43 - й Международный семинар по языкам, автоматов, и программирование : 81: 1-81: 13, DOI : 10,4230 / LIPIcs.ICALP.2016.81 , S2CID 12720136
- Пэ, Сунг Ын (2007), Последовательные и параллельные алгоритмы для обобщенной задачи о максимальном подмассиве (PDF) (докторская диссертация), Университет Кентербери, S2CID 2681670 , архивировано из оригинала (PDF) 26 октября 2017 г..
- Бенгтссон, Фредрик; Чен, Цзинсен (2007 г.), Оптимальное вычисление сегментов с максимальной оценкой (PDF) (Отчет об исследовании), Технологический университет Лулео
- Bentley, Джон (1984), "Программирование Pearls: Методы алгоритм проектирования", коммуникаций АСМ , 27 (9): 865-873, DOI : 10,1145 / 358234,381162 , S2CID 207565329
- Бентли, Джон (май 1989 г.), Programming Pearls (2-е изд.), Ридинг, Массачусетс: Эддисон Уэсли, ISBN 0-201-10331-1
- Птица, Ричард С. (1989), "Алгебраические тождества для расчета программы" (PDF) , Компьютерный журнал , 32 (2): 122-126, DOI : 10,1093 / comjnl / 32.2.122[ мертвая ссылка ]
- Бродал, Герт Стёльтинг; Йоргенсен, Аллан Grønlund (2007), "Линейный алгоритм времени для к задаче максимальных сумм", Математические основы информатики , Lecture Notes в области компьютерных наук, 4708 , Springer-Verlag, стр 442-453,. DOI : 10.1007 / 978 -3-540-74456-6_40.
- Гриз, Дэвид (1982), "Замечание по стандартной стратегии развития Loop Инвариантов и Loops" (PDF) , Наука компьютерного программирования , 2 (3): 207-241, DOI : 10.1016 / 0167-6423 (83) 90015 -1 , ЛВП : 1813/6370
- Такаока, Тадао (2002), "Эффективные алгоритмы для задачи максимального подмассива путем умножения матрицы расстояний", электронные примечания в теоретической информатике , 61 : 191-200, DOI : 10.1016 / S1571-0661 (04) 00313-5.
- Тамаки, Хисао; Токуяма, Такеши (1998), «Алгоритмы для задачи о максимальном подмассиве, основанные на умножении матриц» , Труды 9-го симпозиума по дискретным алгоритмам (SODA) : 446–452 , получено 17 ноября 2018 г.
Внешние ссылки
- ТАН, Лиронг. «Задачи о максимальной сумме смежных подмассивов» (PDF) . Архивировано из оригинального (PDF) 10.10.2015 . Проверено 26 октября 2017 .
- Му, Шин-Ченг (2010). «Проблема максимальной суммы сегмента: ее происхождение и происхождение» .
- «Примечания к проблеме максимального подмассива» . 2012 г.
- www.algorithmist.com
- alexeigor.wikidot.com
- проблема наибольшей подпоследовательной суммы на Розеттском коде
- Страница geeksforgeeks по алгоритму Кадане