Максимальный подмассив

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

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

6

nums = [1]

1

nums = [5, 4, -1, 7, 8]

23

Решение

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

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

Идея решения:

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

Подмассив - это непрерывная часть исходного массива, в которой элементы должны идти один за другим, без пропусков. Любой одиночный элемент - это подмассив. Сам массив целиком - тоже подмассив.

Вот все возможные подмассивы массива [1, 2, 3, 4]:

• [1], [2], [3], [4]
• [1, 2], [2, 3], [3, 4]
• [1, 2, 3], [2, 3, 4]
• [1, 2, 3, 4]

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

В этом решении потребуется три вложенных цикла:

• Первый цикл: левая граница i.
• Второй цикл: правая граница j.
• Третий цикл: считает сумму от i до j.

Это похоже на кубическую сложность и очень неоптимально на наших ограничениях.

Можно заметить, что если мы уже знаем сумму подмассива от i до j, то сумма от i до j+1 - это просто предыдущая сумма + следующий элемент. Третий цикл больше не нужен:

• Первый цикл: левая граница i.
• Второй цикл: расширяем правую границу j и сразу обновляем текущую сумму.

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

n + (n-1) + (n-2) + ... +   2   + 1
1 +   2   +   3   + ... + (n-1) + n

В таком наивном решении мы перебираем квадратичное количество подмассивов. Можем ли мы улучшить это решение?

Каждый элемент массива определенным образом входит в возможные подмассивы. Это либо старт, либо середина, либо конец возможного подмассива. Что, если бы мы могли принимать решение о лучшей сумме на основе текущего элемента и каких-то накопленных знаний о предыдущих элементах, которые мы уже видели? Что нам нужно знать о предыдущих просмотренных элементах? Может быть, это уже накопленная сумма и, возможно, "лучшая сумма", которую удалось собрать до этого момента.

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

Давайте подробнее рассмотрим эту идею. Представьте, что прямо сейчас мы смотрим на элемент с индексом i.

Задайте себе вопрос: какие варианты у нас есть для элемента с индексом i?

Этот элемент может продолжать или заканчивать какой-то подмассив с началом в индексе слева от i, либо может начинать новый подмассив со стартом в i.

То есть, элемент nums[i]:

• продолжает текущий подмассив (прибавляем nums[i] к накопленному).
• начинает новый подмассив (выкидываем текущий подмассив и начинаем новый прямо с этого элемента).

Ключевой момент: когда нам выгодно бросить текущую сумму? Только если она стала отрицательной. Если у нас сумма 5, а текущее число -2, мы все равно в плюсе (+3). Это лучше, чем начинать с -2. Если сумма -5, а текущее число 1, то старая сумма просто делает все хуже. Проще ее выкинуть, взять 1 и начать заново.

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

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

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

Таким образом, все, что нам нужно - это текущая сумма подмассива, который мы пытаемся продолжить, и глобальная сумма подмассива, который мы встречали до сих пор. Мы пройдем по всему массиву ровно один раз, обновляя эти суммы, и для каждого элемента массива будем проверять: продолжаем текущую сумму или начинаем новую.

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

Основные шаги:

1. Создаем две переменные: currentSum (текущая сумма) и maxSum (глобальный максимум), обе равные nums[0].
2. Идем циклом по массиву, начиная со второго элемента:
   • Если currentSum + nums[i] больше nums[i], прибавляем nums[i] к нашей накопленной currentSum.
   • Иначе "бросаем все" и начинаем новый подмассив: currentSum = nums[i].
   • Обновляем максимум maxSum.
3. Возвращаем maxSum.

Пример 1:

Как это работает на примере [-2, 1, -3, 4, -1, 2, 1, -5, 4].

1. Начинаем с currentSum = -2, maxSum = -2.

2. Далее видим 1. Что лучше: -2 + 1 = -1 или просто 1? Берем 1, currentSum = 1, maxSum = 1.

3. Число -3. 1 + (-3) = -2 или -3? Продолжаем подмассив, currentSum = -2, maxSum все еще 1.

4. Число 4. -2 + 4 = 2 или 4? Берем 4. currentSum = 4, maxSum = 4.

5. Число -1. 4 + (-1) = 3 или -1? Продолжаем подмассив. currentSum = 3, maxSum = 4.

6. Число 2. 3 + 2 = 5 или 2? Продолжаем подмассив. currentSum = 5, maxSum = 5.

7. Число 1. 5 + 1 = 6 или 1? Продолжаем подмассив. currentSum = 6, maxSum = 6.

8. Число -5. 6 + (-5) = 1 или -5? Продолжаем подмассив. currentSum = 1, maxSum = 6.

9. Число 4. 1 + 4 = 5 или 4? Продолжаем подмассив. currentSum = 5, maxSum = 6.

В итоге получили максимальную сумму 6 на подмассиве [4, -1, 2, 1] (шаг 7).

Оценка сложности

Временная сложность

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

В нашем решении мы проходим по массиву ровно один раз с помощью одного цикла. Каждая итерация цикла выполняет операции с константным временем.

Таким образом общее количество операций прямо пропорционально количеству элементов в массиве. Это линейная сложность: O(n).

Пространственная сложность

Мы используем фиксированное количество дополнительной памяти, которое не зависит от размера входного массива.

Для решения нам требуется только несколько переменных типа int, то есть это константная сложность: O(1).

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

Код решения

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

func maxSubArray(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	currentSum := nums[0]
	maxSum := nums[0]
	for i := 1; i < len(nums); i++ {
        // продолжить текущую сумму или начать заново с nums[i]
        currentSum = max(currentSum + nums[i], nums[i])
 
    	// обновляем глобальный максимум, если текущая сумма лучше
    	maxSum = max(maxSum, currentSum)
    }
    return maxSum
 
}
 

Итоги

Задача максимального подмассива - это фундаментальный пример того, как можно оптимизировать решение с квадратичного времени O(n^2) до линейного O(n).

1. Суть алгоритма Кадана: в каждой точке массива мы принимаем решение продолжить текущую сумму или начать новую. Это решение зависит исключительно от текущей суммы.
2. Эффективность:
   • Временная сложность: O(n), так как массив просматривается один раз.
   • Пространственная сложность: O(1), так как нам нужно две переменные для хранения текущей и максимальной сумм.
3. Граничные случаи:
   • Пустой массив: требует предварительной проверки (возврат 0 или выброс исключения).
   • Только отрицательные числа: алгоритм корректно вернет значение самого "большого" (наименее отрицательного) элемента, так как на каждом шаге он будет предпочитать одно число сумме этого числа с другим отрицательным числом.
4. Оптимальное решение: сочетает простоту и эффективность. Этот алгоритм важно знать для интервью, и, кроме того, это ценный инструмент в арсенале любого разработчика.