Maximum Subarray

+10

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

Функция

maxSubArray(nums: integer-array) → integer

numsinteger-array: список целых чисел, содержащий как минимум один элемент
Возвращаетinteger: наибольшая сумма непустой последовательности соседних элементов

Ограничения

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴
Ответ всегда помещается в 32-разрядное целое число со знаком.

Примеры

Ввод: nums = [2, -4, 3, -1, 5, -6, 1]
Вывод: 7
Пояснение: Сумма последовательности [3, -1, 5] равна 7. Если растянуть её влево, добавятся -4, а затем 2; чистый убыток составит 2. Если растянуть её вправо, добавятся -6, а затем 1; чистый убыток составит 5. Ни одна другая последовательность не даёт лучшего результата.

Дополнительный вопрос

Можно ли также решить эту задачу методом «разделяй и властвуй» за O(n log n), разделив список пополам и обработав серии, пересекающие середину?

Решение

Список из n чисел содержит примерно n²/2 подмассивов — слишком много, чтобы проверять их по одному для 10^5 элементов. Сложность заключается в отрицательных числах: последовательность должна сохранять отрицательный элемент, если последующие элементы компенсируют его, и отбрасывать всё до него, если этого не происходит. Алгоритм Кадане делает этот выбор для каждого элемента с помощью одного сравнения.

Суммируйте каждый подмассив

Верно, но не успевает на самых больших тестах

Идея

У каждого подмассива есть первый индекс left и последний индекс right, поэтому перебор каждой пары позволит найти лучший вариант. Зафиксируй left и двигай right вперёд, добавляя каждый новый элемент к текущей total: для каждого подмассива требуется одно сложение, и третий цикл не нужен.

Но это всё равно около n²/2 пар — пять миллиардов сложений для 10^5 элементов.

Алгоритм

Установи best равным первому элементу.
Для каждого начального индекса left установи текущий total равным 0.
Перемещай right от left до конца списка и добавляй nums[right] к total.
После каждого сложения сохраняй total в best, если он больше.
Верни best.

def maxSubArray(nums):
    best = nums[0]
    for left in range(len(nums)):
        total = 0
        # Grow the subarray that starts at left by one element at a time
        for right in range(left, len(nums)):
            total += nums[right]
            best = max(best, total)
    return best

Алгоритм Кадане

Идея

Наилучший отрезок, заканчивающийся на индексе i, — это либо только nums[i], либо наилучший отрезок, заканчивающийся на i-1, с добавленным к нему nums[i], поскольку ни один другой отрезок, заканчивающийся на i-1, не имеет большей суммы. Поэтому храни одно число endingHere — наилучшую сумму отрезка, заканчивающегося на текущем элементе. Для следующего элемента x оно становится большим из значений x и endingHere + x: пока сумма отрезка положительна, ты продолжаешь его, а когда она становится нулевой или отрицательной, начинаешь заново с x.

Наилучший подмассив заканчивается где-то, поэтому ответ — наибольшее значение, которое принимает endingHere. В первом примере оно принимает значения 2, -2, 3, 2, 7, 1, 2, и ответ равен 7.

Алгоритм

Установи endingHere и best равными первому элементу.
Для каждого следующего элемента x установи endingHere равным большему из x и endingHere + x.
Установи best равным большему из best и endingHere.
После последнего элемента верни best.

def maxSubArray(nums):
    current = nums[0]
    best = nums[0]
    for i in range(1, len(nums)):
        current = max(nums[i], current + nums[i])
        best = max(best, current)
    return best

Ловушки и крайние случаи

Начало с best, равного 0. Для [-3, -1, -2] тогда возвращается 0 вместо -1. Начинайте с первого элемента.
Ограничение текущей суммы выражением max(0, endingHere + x). Для того же списка это не сработает; вместо этого сравнивайте с x.
Суммирование только положительных чисел. Элементы должны быть соседними, поэтому в первом примере результат равен 7, а не 2 + 3 + 5 + 1 = 11.
Начало цикла с индекса 1 без присваивания nums[0] переменным endingHere и best. Для списка из одного элемента, например [-5], нужно вернуть -5.

Частые вопросы3

Что такое алгоритм Кадане?

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

Какова временная сложность алгоритма для поиска максимального подмассива?

Алгоритм Кадане работает за время O(n) и использует O(1) дополнительной памяти, поскольку каждый элемент просматривается один раз. Проверка каждого подмассива с помощью текущей суммы занимает O(n²), а вычисление суммы каждого подмассива с нуля — O(n³).

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

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

def maxSubArray(nums):
    # Напишите код здесь

Тест #1

Тест #2

Аргумент

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

Ожидаемый вывод