Максимальная абсолютная сумма подмассива

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

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

5

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

8

Решение

Мы уже знакомы с классическим алгоритмом Кадана для поиска максимальной суммы подмассива из разбора: Максимальный подмассив.

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

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

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

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

Давайте здесь остановимся и немного подумаем, как мы могли бы расширить логику алгоритма Кадана, чтобы эффективно решить этот вариант?

Задайте себе вопрос: как бы мы решали задачу, если бы нужно было искать не максимальную, а минимальную сумму подмассива?

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

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

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

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

1. Создаем переменные currentMax (для текущего максимума) и currentMin (для текущего минимума), а также absMax для хранения глобального результата. Все они в начале равны 0.
2. Идем циклом по массиву:
   • Обновляем currentMax, выбирая большее между nums[i] и currentMax + nums[i] (классический Кадан).
   • Обновляем currentMin, выбирая меньшее между nums[i] и currentMin + nums[i] (зеркальный Кадан).
   • Обновляем absMax, сравнивая текущий absMax с currentMax и абсолютным значением currentMin.
3. Возвращаем absMax.

После обсуждения идеи решения сделаем ручной прогон на примере и проверим наш подход.

Пример 1:

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

1. На старте: currentMax = 0, currentMin = 0, absMax = 0.

2. Далее видим 1:

   • currentMax = max(1, 0+1) = 1
   • currentMin = min(1, 0+1) = 1
   • absMax = max(0, 1, 1) = 1

3. Видим -3:

   • currentMax = max(-3, 1-3) = -2
   • currentMin = min(-3, 1-3) = -3
   • absMax = max(1, -2, 3) = 3

4. Число 2:

   • currentMax = max(2, -2+2) = 2
   • currentMin = min(2, -3+2) = -1
   • absMax = max(3, 2, 1) = 3

5. Число 3:

   • currentMax = max(3, 2+3) = 5
   • currentMin = min(3, -1+3) = 2
   • absMax = max(3, 5, 2) = 5

6. Число -4:

   • currentMax = max(-4, 5-4) = 1
   • currentMin = min(-4, 2-4) = -2
   • absMax = max(5, 1, 2) = 5

Итог:

• Максимальная положительная сумма была достигнута на шаге 5 (подмассив [2, 3]), результат 5.
• Минимальная отрицательная сумма -3 была на шаге 3 (подмассив [-3]), абсолютное значение 3.
• Финальный ответ: 5.

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

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

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

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

Таким образом, это линейная сложность: O(n).

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

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

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

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

Код решения

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

func maxAbsoluteSum(nums []int) int {
    currentMax, currentMin, absMax := 0, 0, 0
 
    for i := 0; i < len(nums); i++ {
        currentMax = max(nums[i], currentMax + nums[i])
        currentMin = min(nums[i], currentMin + nums[i])
 
        absMax = max(absMax, max(currentMax, abs(currentMin)))
    }
 
    return absMax
 
}
 

Итоги

Задача поиска максимальной абсолютной суммы подмассива - это отличный пример того, как базовая концепция (алгоритм Кадана) адаптируется под более гибкие условия.

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