Компьютерный центр г. Светлогорска

Пусть дан массив \(array\), состоящий из \(n\) чисел; наша первая задача заключается в том, чтобы вычислить максимальную сумму подмассивов, т. е. наибольшую возможную сумму последовательных элементов. Задача приобретает интерес, когда в массиве встречаются элементы с отрицательными значениями. Ниже показаны массив и его подмассив с максимальной суммой.

Подмассивом с максимальной суммой является \([2, 4, –3, 5, 2]\). Его сумма равна \(10\).

Решение со сложностью \(O(n^3)\)

Задачу можно решить в лоб: перебрать все возможные подмассивы, вычислить сумму элементов в каждом подмассиве и запомнить максимальную сумму. Этот алгоритм реализован в следующем коде:

best = array[0]
for a in range(n):
    for b in range(n):
        su = 0
        for k in range(a, b + 1):
            su += array[k]
        best = max(best, su)
print(f"{best}")

В переменных \(a\) и \(b\) хранятся первый и последний индекс подмассива, а в переменную \(su\) записывается сумма его элементов. В переменной \(best\) хранится максимальная сумма, найденная в процессе просмотра. Временная сложность этого алгоритма равна \(O(n^3)\), поскольку налицо три вложенных цикла, в которых перебираются входные данные.

Решение со сложностью \(O(n^2)\)

Алгоритм легко сделать более эффективным, исключив один цикл. Для этого будем вычислять сумму одновременно со сдвигом правого конца подмассива. В результате получается такой код:

best = array[0]
for a in range(n):
    su = 0
    for b in range(n):
        su += array[b]
        best = max(best, su)
print(f"{best}")

После подобного изменения временная сложность становится равна \(O(n^2)\).

Решение со сложностью \(O(n)\)

Оказывается, что задачу можно решить и за время \(O(n)\), т. е. достаточно и одного цикла. Идея в том, чтобы для каждой позиции массива вычислять максимальную сумму подмассива, заканчивающегося в этой позиции. Тогда для получения окончательного ответа достаточно будет взять максимум из этих сумм.

Рассмотрим подзадачу нахождения подмассива с максимальной суммой, заканчивающегося в позиции \(k\). Есть две возможности:

1. Подмассив состоит из единственного элемента в позиции \(k\).
2. Подмассив состоит из подмассива, заканчивающегося в позиции \(k-1\), за которым следует элемент в позиции \(k\).

Во втором случае, поскольку мы ищем подмассив с максимальной суммой, сумма подмассива, заканчивающегося в позиции \(k-1\), также должна быть максимальной. Таким образом, задачу можно решить эффективно, если вычислять сумму максимального подмассива для каждой позиции последнего элемента слева направо.

Алгоритм реализуется следующей программой:

best = array[0]
su = 0
for k in range(n):
    su = max(array[k], su + array[k])
    best = max(best, su)
print(f"{best}")

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

Сравнение эффективности

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

Сравнение показывает, что все алгоритмы работают быстро, если размер входных данных мал, но по мере возрастания размера расхождение во времени становится очень заметным. Алгоритм со сложностью \(O(n^3)\) замедляется, когда \(n = 10^4\), а алгоритм со сложностью \(O(n^2)\) — при \(n = 10^5\). И лишь алгоритм со сложностью \(O(n)\) даже самые большие входные данные обрабатывает мгновенно.

Следующая наша задача будет такой: сколькими способами можно поставить на доску \(n \times n\) двух ферзей, так чтобы они не били друг друга. На рисунке ниже показано, что на доске \(3 \times 3\) это можно сделать \(8\) способами.

Обозначим \(q(n)\) количество расстановок на доске \(n \times n\). Например, \(q(3) = 8\), а в таблице ниже приведены значения \(q(n)\) для \(1 \leq n \leq 10\).

Конечно, задачу можно решить по-простому: перебрать все возможные расстановки двух ферзей и подсчитать те, в которых ферзи не бьют друг друга. Временная сложность такого алгоритма \(O(n^4)\), поскольку позицию первого ферзя можно выбрать \(n^2\) способами, а затем поставить второго ферзя  \(n^2-1\)  способами.

Так как число расстановок растет очень быстро, алгоритм их подсчета поодиночке будет работать слишком медленно для больших \(n\). Следовательно, для создания эффективного алгоритма нужно придумать способ подсчета расстановок группами. Полезно отметить, что очень просто подсчитать, сколько клеток бьет один ферзь. Во-первых, он всегда бьет \(n-1\) клеток по горизонтали и \(n-1\) клеток по вертикали. Далее по обеим диагоналям ферзь бьет \(d-1\) клеток, где \(d\) — число клеток на диагонали. С учетом всего этого для вычисления числа клеток, в которые можно поставить второго ферзя, нужно время \(O(1)\), так что мы получаем алгоритм с временной сложностью \(O(n^2)\).

К задаче можно подойти и по-другому, попытавшись найти рекуррентную формулу для подсчета расстановок, т. е. ответить на вопрос: как, зная \(q(n)\), вычислить \(q(n+1)\)?

Чтобы получить рекурсивное решение, обратим внимание на последние горизонталь и вертикаль доски \(n \times n\).

Во-первых, число расстановок, в которых на последней горизонтали и на последней вертикали нет ферзей, равно \(q(n-1)\). Во-вторых, общее число позиций ферзя на последней горизонтали и на последней вертикали равно \(2n - 1\). Находящийся в этих позициях ферзь бьет \(3(n-1)\) клеток, поэтому для второго ферзя остается \(n^2 − 3(n − 1) – 1\) позиций. Наконец, существует \((n-1)(n-2)\) расстановок, в которых оба ферзя находятся на последней горизонтали или на последней вертикали. Поскольку эти расстановки посчитаны дважды, их количество надо вычесть. Объединив все вместе, получаем рекуррентную формулу:

\(q(n) = q(n-1) + (2n-1)(n^2-3(n-1)-1) - (n-1)(n-2)\)

\( = q(n-1) + (2n-1)^2(n-2)\)

и вместе с ней решение сложности \(O(n)\).

Однако же существует и замкнутая формула для этой функции:

которую можно доказать по индукции, пользуясь рекуррентной формулой. А раз так, то задачу можно решить за время \(O(1)\).