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

В задаче о подмассиве с максимальной суммой требуется найти непрерывный подмассив в одномерном массиве чисел, сумма элементов которого максимальна. Например, в массиве [-2, 1, -3, 4, -1, 2, 1, -5, 4] подмассив [4, -1, 2, 1] даёт максимальную сумму, равную 6. При переборе всех подмассивов методом полного перебора выполняется O(n²) операций, а алгоритм Кадане решает эту задачу за O(n).

Алгоритм Кадане выполняет один проход по массиву, поддерживая текущую сумму в current_sum. На каждом элементе нужно решить: лучше ли продолжить существующий подмассив или начать новый с этого элемента? Если current_sum становится отрицательной, она только ухудшит любой будущий подмассив, поэтому следует начать заново. Рекуррентное соотношение имеет вид current_sum = max(num, current_sum + num).

Проследим работу алгоритма Кадане на массиве [-2, 1, -3, 4, -1, 2, 1, -5, 4]: начальные значения curr=-2, max=-2. При 1: curr=max(1,-2+1)=1, max=1. При -3: curr=max(-3,1-3)=-2, max=1. При 4: curr=max(4,-2+4)=4, max=4. При -1: curr=3, max=4. При 2: curr=5, max=5. При 1: curr=6, max=6. При -5: curr=1. При 4: curr=5, max=6. Алгоритм правильно определяет, что оптимальным является подмассив, заканчивающийся на индексе 6.

Если на собеседовании Вас попросят вернуть сам подмассив, а не только его сумму, необходимо отслеживать начальный и конечный индексы. При начале нового подмассива (если num > current_sum + num) обновляйте temp_start. При обновлении max_sum сохраните temp_start в start, а текущий индекс — в end. Это добавляет O(1) накладных расходов к тому же алгоритму со сложностью O(n).

Задача о подмассиве с максимальным произведением сложнее варианта с суммой из-за отрицательных чисел. Два отрицательных числа при умножении дают положительный результат, поэтому очень маленькое отрицательное произведение после умножения на другое отрицательное число может стать максимальным. Для [2, 3, -2, 4] ответ равен 6 ([2, 3]). Для [-2, 0, -1] ответ равен 0. На каждом шаге необходимо отслеживать как максимальное, так и минимальное произведение.

Главная идея такова: в каждой позиции текущее максимальное произведение является одним из значений num, max_so_far * num или min_so_far * num (последний вариант полезен, когда отрицательное число превращает минимум в максимум). Аналогично вычисляется минимум. Обновляйте одновременно cur_max и cur_min, используя предыдущие значения, чтобы на этом же шаге не использовать уже обновлённые значения.

Рассмотрим [-3, -10, 5]. После обработки -3: максимум=-3, минимум=-3. После -10: кандидаты — (-10, 30, 30) → максимум=30, минимум=-10. После 5: кандидаты — (5, 150, -50) → максимум=150. Без отслеживания min_prod Вы пропустили бы изменение знака, которое происходит, когда очень большое по модулю отрицательное минимальное произведение умножается на другое отрицательное число. Всегда вычисляйте max и min на основе одних и тех же предыдущих значений, чтобы избежать ошибки чтения устаревшего значения.

Ноль в массиве сбрасывает оба текущих произведения в ноль, фактически разделяя массив на независимые подмассивы. При num = 0 и max_prod * 0 = 0, и min_prod * 0 = 0, поэтому все три кандидата становятся равны 0, а предыдущий максимальный результат сохраняется. Специальный код не требуется — общая формула естественным образом обрабатывает нули.

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

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

И алгоритм Кадане (максимальная сумма), и отслеживание минимума и максимума (максимальное произведение) работают за O(n) времени и используют O(1) памяти. Советы для собеседования: (1) Для максимальной суммы упомяните альтернативный подход «разделяй и властвуй» со сложностью O(n log n), чтобы показать широту знаний. (2) Для максимального произведения подчеркните, что min_prod и max_prod нужно одновременно обновлять на основе предыдущих значений, чтобы не использовать устаревшие данные. (3) Всегда уточняйте: может ли массив быть пустым? Должен ли подмассив быть непустым? (Да, по принятому соглашению он должен быть непустым.)

Проверьте, насколько Вы понимаете концепции курса «Структуры данных и алгоритмы — подготовка к собеседованию по программированию», рассмотренные в этом уроке.

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