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

Визуализация того, как изменяются подмассивы в зависимости от начальной и конечной позиции выборки. Каждый возможный непрерывный подмассив представлен точкой на цветной линии. Координата Y этой точки представляет собой сумму выборки. Его координата x представляет конец выборки, а крайняя левая точка этой цветной линии представляет начало выборки. В данном случае массив, из которого берутся выборки, — [2, 3, -1, -20, 5, 10].

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

Формально задача состоит в нахождении индексов $i$ и $j$ с $1\leq i\leq j\leq n$, такой, что сумма

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

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

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

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

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

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

История

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

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

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

Приложения

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

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

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

Алгоритм Кадане

Пустые подмассивы не допускаются

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

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

Таким образом, проблему можно решить с помощью следующего кода: выраженный на Python .

def max_subarray(numbers):
    """Find the largest sum of any contiguous subarray."""
    best_sum = - infinity
    current_sum = 0
    for x in numbers:
        current_sum = max(x, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum

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

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

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

Допускаются пустые подмассивы

showПример запуска
Execution of Kadane's algorithm on the above example array. Blue: subarray with largest sum ending at i; green: subarray with largest sum encountered so far; a lower case letter indicates an empty array; variable i is left implicit in Python code.

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

    best_sum = 0;

и строка 6 в цикле for current_sum должен быть обновлен как max(0, current_sum + x).

        current_sum = max(0, current_sum + x)

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

Вычисление лучшей позиции подмассива

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

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

Сложность

Сложность выполнения алгоритма Кадане составляет $O(n)$ и его пространственная сложность равна $O(1)$.

Обобщения

Аналогичные проблемы могут возникнуть и для многомерных массивов, но их решения более сложны; см., например, Такаока (2002) . Бродал и Йоргенсен (2007) показали, как найти k крупнейших сумм подмассивов в одномерном массиве за оптимальное время. $O(n+k)$.

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

См. также

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

Ссылки

• Алвес, Карлос Э.Р.; Касерес, Эдсон; Сонг, Сианг В. (2004), «Алгоритмы BSP/CGM для максимальной подпоследовательности и максимального подмассива», в Кранцльмюллере, Дитере; Качук, Питер; Донгарра, Джек Дж. (ред.), «Последние достижения в области параллельных виртуальных машин и интерфейса передачи сообщений», 11-е собрание европейской группы пользователей PVM/MPI, Будапешт, Венгрия, 19–22 сентября 2004 г., материалы , конспекты лекций по информатике, том. 3241, Springer, стр. 139–146, номер документа : 10.1007/978-3-540-30218-6_24 , ISBN.  978-3-540-23163-9
• Бакурсс, Артурс; Диккала, Нишант; Цамос, Христос (2016), «Результаты жесткости для прямоугольников максимального веса», Proc. 43-й международный коллоквиум по автоматам, языкам и программированию : 81:1–81:13, doi : 10.4230/LIPIcs.ICALP.2016.81 , S2CID   12720136
• Бэ, Сунг Ын (2007), Последовательные и параллельные алгоритмы для задачи обобщенного максимального подмассива (PDF) (докторская диссертация), Университет Кентербери, S2CID   2681670 , заархивировано из оригинала (PDF) 26 октября 2017 г.
• Пэ, Сон Ын; Такаока, Тадао (2006), «Улучшенные алгоритмы для задачи \emph{K}-максимального подмассива», 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-е изд.), Ридинг, Массачусетс: Аддисон Уэсли, 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
• Руццо, Уолтер Л.; Томпа, Мартин (1999), «Алгоритм линейного времени для поиска всех подпоследовательностей с максимальным результатом» , в Ленгауэре, Томасе; Шнайдер, Рейнхард; Борк, Пер; Брютлаг, Дуглас Л.; Глазго, Дженис И.; Мьюз, Ханс-Вернер; Циммер, Ральф (ред.), Труды Седьмой Международной конференции по интеллектуальным системам для молекулярной биологии, 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), «Алгоритмы максимального подмассива для использования в астрономических изображениях», Journal of Electronic Imaging , 22 (4): 043011, Bibcode : 2013JEI....22d3011W , doi : 10.1117/1.2.42.13.

Внешние ссылки

• ТАН, Лиронг. «Задачи о максимальной сумме смежных подмассивов» (PDF) . Архивировано из оригинала (PDF) 10 октября 2015 г. Проверено 26 октября 2017 г.
• Му, Шин-Ченг (2010). «Задача о максимальной сумме сегментов: ее происхождение и вывод» .
• «Заметки о задаче о максимальном подмассиве» . 2012.
• www.algorithmist.com
• alexeigor.wikidot.com
• задача о наибольшей последовательной сумме в Розеттском коде
• Страница geeksforgeeks об алгоритме Кадане