MAXimal

добавлено: 23 Aug 2011 12:40
редактировано: 15 Jul 2014 22:21

Поиск подотрезка массива с максимальной/минимальной суммой

Здесь мы рассмотрим задачу о поиске подотрезка массива с максимальной суммой ("maximum subarray problem" на английском), а также некоторые её вариации (в том числе алгоритм решения варианта этой задачи в режиме онлайн — описанный автором алгоритма — KADR (Ярослав Твердохлеб)).

Постановка задачи

Дан массив чисел $a[1 \ldots n]$ . Требуется найти такой его подотрезок $a[l \ldots r]$ , что сумма на нём максимальна:

$\max_{ 1 \le l \le r \le n } \sum_{i=l}^{r} a[i].[...]$

Например, если бы все числа массива $a[]$ были бы неотрицательными, то в качестве ответа можно было бы взять весь массив. Решение нетривиально, когда массив может содержать как положительные, так и отрицательные числа.

Понятно, что задача о поиске минимального подотрезка — по сути та же самая, достаточно лишь изменить знаки всех чисел на противоположные.

Алгоритм 1

Здесь мы рассмотрим практически очевидный алгоритм. (Дальше мы рассмотрим другой алгоритм, который чуть сложнее придумать, однако его реализация получается ещё короче.)

Описание алгоритма

Алгоритм весьма прост.

Введём для удобства обозначение: $s[i] = \sum_{j=1}^{i} a[j]$ . Т.е. массив $s[i]$ — это массив частичных сумм массива $a[]$ . Также положим значение $s[0] = 0$ .

Будем теперь перебирать индекс $r = 1 \ldots n$ , и научимся для каждого текущего значения $r$ быстро находить оптимальное $l$ , при котором достигается максимальная сумма на подотрезке $[l; r]$ .

Формально это означает, что нам надо для текущего $r$ найти такое $l$ (не превосходящее $r$ ), чтобы величина $s[r] - s[l-1]$ была максимальной. После тривиального преобразования мы получаем, что нам надо найти в массиве $s[]$ минимум на отрезке $[0;r-1]$ .

Отсюда мы сразу получаем алгоритм решения: мы просто будем хранить, где в массиве $s[]$ находится текущий минимум. Используя этот минимум, мы за $O(1)$ находим текущий оптимальный индекс $l$ , а при переходе от текущего индекса $r$ к следующему мы просто обновляем этот минимум.

Очевидно, этот алгоритм работает за $O(n)$ и асимптотически оптимален.

Реализация

Для реализации нам даже не понадобится явно хранить массив частичных сумм $s[]$ — от него нам будет требоваться только текущий элемент.

Реализация приводится в 0-индексированных массивах, а не в 1-нумерации, как было описано выше.

Приведём сначала решение, которое находит просто численный ответ, не находя индексы искомого отрезка:

int ans = a[0],
	sum = 0,
	min_sum = 0;
for (int r=0; r<n; ++r) {
	sum += a[r];
	ans = max (ans, sum - min_sum);
	min_sum = min (min_sum, sum);
}

Теперь приведём полный вариант решения, который параллельно с числовым решением находит границы искомого отрезка:

int ans = a[0],
	ans_l = 0,
	ans_r = 0,
	sum = 0,
	min_sum = 0,
	min_pos = -1;
for (int r=0; r<n; ++r) {
	sum += a[r];
 
	int cur = sum - min_sum;
	if (cur > ans) {
		ans = cur;
		ans_l = min_pos + 1;
		ans_r = r;
	}
 
	if (sum < min_sum) {
		min_sum = sum;
		min_pos = r;
	}
}

Алгоритм 2

Здесь мы рассмотрим другой алгоритм. Его чуть сложнее понять, но зато он более элегантен, чем приведённый выше, и реализуется чуть-чуть короче. Этот алгоритм был предложен Джеем Каданом (Jay Kadane) в 1984 г.

Описание алгоритма

Сам алгоритм выглядит следующим образом. Будем идти по массиву и накапливать в некоторой переменной $s$ текущую частичную сумму. Если в какой-то момент $s$ окажется отрицательной, то мы просто присвоим $s=0$ . Утверждается, что максимум из всех значений переменной $s$ , случившихся за время работы, и будет ответом на задачу.

Докажем этот алгоритм.

В самом деле, рассмотрим первый момент времени, когда сумма $s$ стала отрицательной. Это означает, что, стартовав с нулевой частичной суммы, мы в итоге пришли к отрицательной частичной сумме — значит, и весь этот префикс массива, равно как и любой его суффикс имеют отрицательную сумму. Следовательно, от всего этого префикса массива в дальнейшем не может быть никакой пользы: он может дать только отрицательную прибавку к ответу.

Однако этого недостаточно для доказательства алгоритма. В алгоритме мы, фактически, ограничиваемся в поиске ответа только такими отрезками, которые начинаются непосредственно после мест, когда случалось $s<0$ .

Но, в самом деле, рассмотрим произвольный отрезок $[l;r]$ , причём $l$ не находится в такой "критической" позиции (т.е. $l > p+1$ , где $p$ — последняя такая позиция, в которой $s<0$ ). Поскольку последняя критическая позиция находится строго раньше, чем в $l-1$ , то получается, что сумма $a[p+1 \ldots l-1]$ неотрицательна. Это означает, что, сдвинув $l$ в позицию $p+1$ , мы увеличим ответ или, в крайнем случае, не изменим его.

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

Реализация

Как и в алгоритме 1, приведём сначала упрощённую реализацию, которая ищет только числовой ответ, не находя границ искомого отрезка:

int ans = a[0],
	sum = 0;
for (int r=0; r<n; ++r) {
	sum += a[r];
	ans = max (ans, sum);
	sum = max (sum, 0);
}

Полный вариант решения, с поддержанием индексов-границ искомого отрезка:

int ans = a[0],
	ans_l = 0,
	ans_r = 0,
	sum = 0,
	minus_pos = -1;
for (int r=0; r<n; ++r) {
	sum += a[r];
 
	if (sum > ans) {
		ans = sum;
		ans_l = minus_pos + 1;
		ans_r = r;
	}
 
	if (sum < 0) {
		sum = 0;
		minus_pos = r;
	}
}

Смежные задачи

Поиск максимального/минимального подотрезка с ограничениями

Если в условии задачи на искомый отрезок $[l;r]$ накладываются дополнительные ограничения (например, что длина $r-l+1$ отрезка должна находиться в заданных пределах), то описанный алгоритм скорее всего легко обобщается на эти случаи — так или иначе, задача будет по-прежнему заключаться в поиске минимума в массиве $s[]$ при заданных дополнительных ограничениях.

Двумерный случай задачи: поиск максимальной/минимальной подматрицы

Описанная в данной статье задача естественно обобщается на большие размерности. Например, в двумерном случае она превращается в поиск такой подматрицы $[l_1 \ldots r_1; l_2 \ldots r_2]$ заданной матрицы, которая имеет максимальную сумму чисел в ней.

Из описанного выше решения для одномерного случая легко получить решение за $O(n^3)$ : переберём $l_1$ и $r_1$ , и посчитаем массив сумм с $l_1$ по $r_1$ в каждой строке матрицы; мы пришли к одномерной задаче поиска индексов $l_2$ и $r_2$ в этом массиве, которую уже можно решать за линейное время.

Более быстрые алгоритмы решения этой задачи хотя и известны, однако они не сильно быстрее $O(n^3)$ , и при этом весьма сложны (настолько сложны, что по скрытой константе многие из них уступают тривиальному алгоритму при всех разумных ограничениях). По всей видимости, лучший из известных алгоритмов работает за $O \left( n^3 \frac{ \log^3 \log n }{ \log^2 n} \right)$ (T. Chan 2007 "More algorithms for all-pairs shortest paths in weighted graphs").

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

Поиск подотрезка с максимальной/минимальной средней суммой

Эта задача заключается в том, что надо найти такой отрезок $[l;r]$ , чтобы среднее значение на нём было максимальным:

$\max_{l \le r} \frac{ 1 }{ r-l+1 } \sum_{i=l}^{r}[...]$

Конечно, если на искомый отрезок $[l;r]$ по условию не наложено других условий, то решением всегда будет являться отрезок длины $1$ в точке-максимуме массива. Задача имеет смысл, только если имеются дополнительные ограничения (например, длина искомого отрезка ограничена снизу).

В таком случае применим стандартный приём при работе с задачами о среднем значении: будем подбирать искомую максимальную среднюю величину двоичным поиском.

Для этого нам надо научиться решать такую подзадачу: дано число $x$ , и надо проверить, есть ли подотрезок массива $a[]$ (конечно, удовлетворяющий всем дополнительным ограничениям задачи), на котором среднее значение больше $x$ .

Чтобы решить эту подзадачу, отнимем $x$ от каждого элемента массива $a[]$ . Тогда наша подзадача фактически превращается в такую: есть или нет в данном массиве подотрезок положительной суммы. А эту задачу мы уже умеем решать.

Таким образом, мы получили решение за асимпотику $O (T(n) \log W)$ , где $W$ — требуемая точность, $T(n)$ — время решения подзадачи для массива длины $n$ (которое может варьироваться в зависимости от конкретных накладываемых дополнительных ограничений).

Решение задачи в режиме онлайн

Условие задачи таково: дан массив из $n$ чисел, а также дано число $L$ . Поступают запросы вида $(l,r)$ , и в ответ на запрос требуется найти подотрезок отрезка $[l;r]$ длины не менее $L$ с максимально возможным средним арифметическим.

Алгоритм решения этой задачи достаточно сложен. Автор данного алгоритма — KADR (Ярослав Твердохлеб) — описал данный алгоритм в своём сообщении на форуме.