Задача о максимальном подмассиве

В информатике задача максимальной суммы подмассива , также известная как задача максимальной суммы сегмента , — это задача нахождения непрерывного подмассива с наибольшей суммой в заданном одномерном массиве A[1...n] чисел. Она может быть решена во времени и пространстве.${\displaystyle O(n)}$${\displaystyle O(1)}$

Формально задача состоит в том, чтобы найти индексы и при , такие, чтобы сумма${\displaystyle я}$${\displaystyle j}$${\displaystyle 1\leq i\leq j\leq n}$

${\displaystyle \sum _{x=i}^{j}A[x]}$

максимально возможное значение. (Некоторые формулировки задачи также позволяют рассматривать пустой подмассив; по соглашению сумма всех значений пустого подмассива равна нулю.) Каждое число во входном массиве A может быть положительным, отрицательным или нулевым. ^[1]

Например, для массива значений [−2, 1, −3, 4, −1, 2, 1, −5, 4] непрерывный подмассив с наибольшей суммой — это [4, −1, 2, 1] с суммой 6.

Некоторые свойства этой проблемы:

1. Если массив содержит все неотрицательные числа, то задача тривиальна: максимальный подмассив — это весь массив.
2. Если массив содержит все неположительные числа, то решением является любой подмассив размера 1, содержащий максимальное значение массива (или пустой подмассив, если это разрешено).
3. Несколько различных подмассивов могут иметь одинаковую максимальную сумму.

Хотя эту задачу можно решить с помощью нескольких различных алгоритмических методов, включая метод грубой силы, ^[2] «разделяй и властвуй», ^[3] динамическое программирование ^[4] и сведение к кратчайшим путям, простой однопроходный алгоритм, известный как алгоритм Кадане, решает ее эффективно.

Задача максимального подмассива была предложена Ульфом Гренадером в 1977 году как упрощенная модель для оценки максимального правдоподобия шаблонов в оцифрованных изображениях. ^[5]

Гренандер хотел найти прямоугольный подмассив с максимальной суммой в двумерном массиве действительных чисел. Алгоритм грубой силы для двумерной задачи выполняется за время O ( n ⁶ ); поскольку это было непозволительно медленно, Гренандер предложил одномерную задачу, чтобы получить представление о ее структуре. Гренандер вывел алгоритм, который решает одномерную задачу за время O ( n ² ), ^{[примечание 1]} улучшая время выполнения грубой силы O ( n ³ ). Когда Майкл Шамос услышал о задаче, он за одну ночь разработал для нее алгоритм «разделяй и властвуй» за O ( n log n ) . Вскоре после этого Шамос описал одномерную задачу и ее историю на семинаре в Университете Карнеги-Меллона, на котором присутствовал Джей Кадане , который за минуту разработал алгоритм с временем O ( n ) ^{[5] [6] [7]} , который является максимально быстрым. ^{[примечание 2]} В 1982 году Дэвид Грайс получил тот же алгоритм с временем O ( n ) применив «стандартную стратегию» Дейкстры ; ^[8] в 1989 году Ричард Берд вывел его путем чисто алгебраической манипуляции алгоритмом грубой силы, используя формализм Берда–Меертенса . ^[9]

Двумерное обобщение Гренадера может быть решено за время O( n ³ ) либо с помощью алгоритма Кадане в качестве подпрограммы, либо с помощью подхода «разделяй и властвуй». Немного более быстрые алгоритмы, основанные на умножении матриц расстояний, были предложены Тамаки и Токуямой (1998) и Такаокой (2002). Есть некоторые свидетельства того, что не существует значительно более быстрого алгоритма; алгоритм, который решает двумерную задачу максимального подмассива за время O( n ^3−ε ) для любого ε>0, будет подразумевать аналогичный быстрый алгоритм для задачи кратчайших путей для всех пар . ^[10]

Задачи максимального подмассива возникают во многих областях, таких как анализ геномной последовательности и компьютерное зрение .

Анализ геномной последовательности использует алгоритмы максимального подмассива для идентификации важных биологических сегментов белковых последовательностей, которые имеют необычные свойства, путем присвоения баллов точкам внутри последовательности, которые являются положительными, когда присутствует мотив, который нужно распознать, и отрицательными, когда его нет, а затем поиска максимального подмассива среди этих баллов. Эти проблемы включают консервативные сегменты, богатые GC регионы, тандемные повторы, фильтр низкой сложности, домены связывания ДНК и регионы с высоким зарядом. ^[11]

В компьютерном зрении растровые изображения обычно состоят только из положительных значений, для которых задача максимального подмассива тривиальна: результатом всегда является весь массив. Однако после вычитания порогового значения (например, среднего значения пикселя) из каждого пикселя, так что пиксели выше среднего будут положительными, а пиксели ниже среднего будут отрицательными, задача максимального подмассива может быть применена к измененному изображению для обнаружения ярких областей внутри него. ^[12]

Алгоритм Кадане сканирует заданный массив слева направо. На шаге th он вычисляет подмассив с наибольшей суммой, заканчивающейся на ; эта сумма сохраняется в переменной . ^{[примечание 3]} Более того, он вычисляет подмассив с наибольшей суммой в любом месте в , сохраняется в переменной , ^{[примечание 4]} и легко получается как максимум из всех значений , которые были видны до сих пор, см. строку 7 алгоритма.${\displaystyle A[1\ldots n]}$${\displaystyle j}$${\displaystyle j}$current_sum${\displaystyle A[1\ldots j]}$best_sumcurrent_sum

Как инвариант цикла , на шаге th старое значение содержит максимум по всей сумме . Следовательно, ^{[примечание 5]} является максимумом по всей сумме . Чтобы расширить последний максимум, чтобы охватить также случай , достаточно рассмотреть также подмассив singleton . Это делается в строке 6 путем назначения в качестве нового значения , которое после этого содержит максимум по всей сумме .${\displaystyle j}$current_sum${\displaystyle i\in \{1,\ldots ,j-1\}}$${\displaystyle A[i]+\cdots +A[j-1]}$current_sum${\displaystyle +A[j]}$${\displaystyle i\in \{1,\ldots ,j-1\}}$${\displaystyle A[i]+\cdots +A[j]}$${\displaystyle i=j}$${\displaystyle A[j\;\ldots \;j]}$${\displaystyle \max(A[j],}$current_sum${\displaystyle +A[j])}$current_sum${\displaystyle i\in \{1,\ldots ,j\}}$${\displaystyle A[i]+\cdots +A[j]}$

Таким образом, проблему можно решить с помощью следующего кода ^[13] , написанного на языке Python .

def  max_subarray ( числа ): """Найдите наибольшую сумму любого смежного подмассива.""" best_sum  =  float ( '-inf' ) текущая_сумма  =  0 для  x  в  числах : текущая_сумма  =  макс ( х ,  текущая_сумма  +  х ) лучшая_сумма  =  макс ( лучшая_сумма ,  текущая_сумма ) вернуть  лучшую_сумму

Если входные данные не содержат положительных элементов, возвращаемое значение равно наибольшему элементу (т. е. значению, ближайшему к 0), или отрицательной бесконечности, если входные данные были пустыми. Для корректности следует вызывать исключение, когда входной массив пуст, поскольку пустой массив не имеет максимального непустого подмассива. Если массив непустой, его первый элемент можно использовать вместо отрицательной бесконечности, если необходимо избежать смешивания числовых и нечисловых значений.

Алгоритм можно адаптировать к случаю, допускающему пустые подмассивы, или для отслеживания начальных и конечных индексов максимального подмассива.

Этот алгоритм вычисляет максимальный подмассив, заканчивающийся в каждой позиции, из максимального подмассива, заканчивающегося в предыдущей позиции, поэтому его можно рассматривать как случай динамического программирования .

Пример запуска

Оригинальный алгоритм Кадане решает вариант проблемы, когда допускаются пустые подмассивы. ^{[4] [7]} Этот вариант вернет 0, если входные данные не содержат положительных элементов (включая случаи, когда входные данные пусты). Он получается двумя изменениями в коде: в строке 3 best_sumследует инициализировать значением 0 для учета пустого подмассива${\displaystyle A[0\ldots -1]}$

 лучшая_сумма  =  0 ;

и строка 6 в цикле for current_sumдолжна быть обновлена ​​как max(0, current_sum + x). ^{[примечание 6]}

 текущая_сумма  =  макс ( 0 ,  текущая_сумма  +  x )

Как инвариант цикла , на шаге th старое значение содержит максимум по всей сумме . ^{[примечание 7]} Следовательно, является максимумом по всей сумме . Чтобы расширить последний максимум, чтобы охватить также случай , достаточно рассмотреть также пустой подмассив . Это делается в строке 6 путем назначения в качестве нового значения , которое после этого содержит максимум по всей сумме . Проверенные машиной коды C / Frama-C обоих вариантов можно найти здесь.${\displaystyle j}$current_sum${\displaystyle i\in \{1,\ldots ,j\}}$${\displaystyle A[i]+\cdots +A[j-1]}$current_sum${\displaystyle +A[j]}$${\displaystyle i\in \{1,\ldots ,j\}}$${\displaystyle A[i]+\cdots +A[j]}$${\displaystyle i=j+1}$${\displaystyle A[j+1\;\ldots \;j]}$${\displaystyle \макс(0,}$current_sum${\displaystyle +A[j])}$current_sum${\displaystyle i\in \{1,\ldots ,j+1\}}$${\displaystyle A[i]+\cdots +A[j]}$

Алгоритм можно модифицировать, чтобы отслеживать также начальные и конечные индексы максимального подмассива.

Благодаря способу, которым этот алгоритм использует оптимальные подструктуры (максимальный подмассив, заканчивающийся в каждой позиции, вычисляется простым способом из связанной, но меньшей и перекрывающейся подзадачи: максимальный подмассив, заканчивающийся в предыдущей позиции), этот алгоритм можно рассматривать как простой/тривиальный пример динамического программирования .

Сложность выполнения алгоритма Кадане составляет , а его пространственная сложность составляет . ^{[4] [7]}${\displaystyle O(n)}$${\displaystyle O(1)}$

Аналогичные проблемы могут быть поставлены для массивов более высокой размерности, но их решения более сложны; см., например, Takaoka (2002). Brodal & Jørgensen (2007) показали, как найти k наибольших сумм подмассивов в одномерном массиве за оптимальное время .${\displaystyle O(n+k)}$

Максимальная сумма k -непересекающихся подмассивов также может быть вычислена за оптимальное время . ^[14]${\displaystyle O(n+k)}$

• Проблема суммы подмножества

• Alves, Carlos ER; Cáceres, Edson; Song, Siang W. (2004), "BSP/CGM Algorithms for Maximum Subsequence and Maximum Subarray", в Kranzlmüller, Dieter; Kacsuk, Péter; Dongarra, Jack J. (ред.), Recent Advances in Parallel Virtual Machine and Message Passing Interface, 11th European PVM/MPI Users' Group Meeting, Будапешт, Венгрия, 19-22 сентября 2004 г., Труды , Lecture Notes in Computer Science, т. 3241, Springer, стр.  139–146 , doi :10.1007/978-3-540-30218-6_24, ISBN 978-3-540-23163-9
• Бэкурс, Артурс; Диккала, Нишант; Цамос, Христос (2016), «Результаты жестких испытаний на твердость для прямоугольников максимального веса», Труды 43-го Международного коллоквиума по автоматам, языкам и программированию : 81:1–81:13, doi : 10.4230/LIPIcs.ICALP.2016.81 , S2CID  12720136
• Bae, Sung Eun (2007), Последовательные и параллельные алгоритмы для обобщенной задачи максимального подмассива (PDF) (диссертация), Университет Кентербери, S2CID  2681670, заархивировано из оригинала (PDF) 2017-10-26.
• Bae, Sung Eun; Takaoka, Tadao (2006), «Улучшенные алгоритмы для задачи о подмассиве \emph{K}-Maximum», The Computer Journal , 49 (3): 358– 374, doi :10.1093/COMJNL/BXL007
• Бенгтссон, Фредрик; Чен, Джингсен (2007), Оптимальное вычисление сегментов с максимальным счетом (PDF) (Исследовательский отчет), Технологический университет Лулео
• Бентли, Джон (1984), «Жемчужины программирования: методы разработки алгоритмов», Communications of the ACM , 27 (9): 865– 873, doi :10.1145/358234.381162, S2CID  207565329
• Бентли, Джон (май 1989), Programming Pearls (2-е изд.), Рединг, Массачусетс: Addison Wesley, ISBN 0-201-10331-1
• Берд, Ричард С. (1989), «Алгебраические тождества для вычисления программ», The Computer Journal , 32 (2): 122– 126, doi :10.1093/comjnl/32.2.122
• Бродал, Герт Столтинг; Йоргенсен, Аллан Грёнлунд (2007), «Алгоритм с линейным временем для задачи k максимальных сумм», Математические основы информатики, 2007 , Конспекты лекций по информатике, том. 4708, Springer-Verlag, стр.  442–453 , номер документа : 10.1007/978-3-540-74456-6_40, ISBN. 978-3-540-74455-9.
• Грайс, Дэвид (1982), «Заметка о стандартной стратегии разработки инвариантов циклов и циклов» (PDF) , Science of Computer Programming , 2 (3): 207– 241, doi : 10.1016/0167-6423(83)90015-1, hdl : 1813/6370
• Ruzzo, Walter L.; Tompa, Martin (1999), "Линейный алгоритм времени для поиска всех подпоследовательностей с максимальным подсчетом", в Lengauer, Thomas; Schneider, Reinhard; Bork, Peer; Brutlag, Douglas L.; Glasgow, Janice I.; Mewes, Hans-Werner; Zimmer, Ralf (ред.), Труды Седьмой международной конференции по интеллектуальным системам для молекулярной биологии, 6–10 августа 1999 г., Гейдельберг, Германия , AAAI, стр.  234–241
• Такаока, Тадао (2002), «Эффективные алгоритмы для задачи максимального подмассива с помощью умножения матриц расстояний», Electronic Notes in Theoretical Computer Science , 61 : 191– 200, doi : 10.1016/S1571-0661(04)00313-5.
• Тамаки, Хисао; Токуяма, Такеши (1998), «Алгоритмы для задачи максимального подмассива на основе умножения матриц», Труды 9-го симпозиума по дискретным алгоритмам (SODA) : 446–452 , ISBN 978-0-89871-410-4, получено 17 ноября 2018 г.
• Уэдделл, Стивен Джон; Рид, Тристан; Тахер, Мохаммед; Такаока, Тадао (2013), «Алгоритмы максимального подмассива для использования в астрономической визуализации», Журнал электронной визуализации , 22 (4): 043011, Bibcode : 2013JEI....22d3011W, doi : 10.1117/1.JEI.22.4.043011

• TAN, Lirong. "Maximum Contiguous Subarray Sum Problems" (PDF) . Архивировано из оригинала (PDF) 2015-10-10 . Получено 2017-10-26 .
• Му, Шин-Чэн (2010). «Проблема максимальной суммы сегмента: ее происхождение и вывод».
• «Заметки о задаче максимального подмассива». 2012.
• www.algorithmist.com
• alexeigor.wikidot.com
• Проблема наибольшей последующей суммы в Rosetta Code
• Страница geeksforgeeks по алгоритму Кадане