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

Максимальная сумма подмассива: Алгоритм Кадане

Понимание задачи

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

Идея: ведём текущую сумму и максимальную сумму. Если текущая сумма становится отрицательной, начинаем заново.

Оптимальное решение: Динамическое программирование O(n)

def max_subarray(nums: list[int]) -> int:
    """
    Находит максимальную сумму непрерывного подмассива.
    Алгоритм Кадане.
    
    Args:
        nums: список целых чисел
    
    Returns:
        Максимальная сумма подмассива
    """
    # Инварианты:
    # current_sum = максимальная сумма подмассива, заканчивающегося в текущей позиции
    # max_sum = максимальная сумма среди всех подмассивов
    
    max_sum = nums[0]
    current_sum = nums[0]
    
    for i in range(1, len(nums)):
        # Либо продолжаем текущую последовательность, либо начинаем новую
        # Если текущая сумма отрицательна, выгоднее начать заново с nums[i]
        current_sum = max(nums[i], current_sum + nums[i])
        
        # Обновляем максимум
        max_sum = max(max_sum, current_sum)
    
    return max_sum

Пример пошагово для [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

i=0: nums=[-2]
  current_sum = -2
  max_sum = -2

i=1: nums=[1]
  current_sum = max(1, -2+1) = max(1, -1) = 1
  max_sum = max(-2, 1) = 1

i=2: nums=[-3]
  current_sum = max(-3, 1-3) = max(-3, -2) = -2
  max_sum = max(1, -2) = 1

i=3: nums=[4]
  current_sum = max(4, -2+4) = max(4, 2) = 4
  max_sum = max(1, 4) = 4

i=4: nums=[-1]
  current_sum = max(-1, 4-1) = max(-1, 3) = 3
  max_sum = max(4, 3) = 4

i=5: nums=[2]
  current_sum = max(2, 3+2) = max(2, 5) = 5
  max_sum = max(4, 5) = 5

i=6: nums=[1]
  current_sum = max(1, 5+1) = max(1, 6) = 6
  max_sum = max(5, 6) = 6

i=7: nums=[-5]
  current_sum = max(-5, 6-5) = max(-5, 1) = 1
  max_sum = max(6, 1) = 6

i=8: nums=[4]
  current_sum = max(4, 1+4) = max(4, 5) = 5
  max_sum = max(6, 5) = 6

Результат: max_sum = 6 (подмассив [4, -1, 2, 1]) ✓

Сложность:

• Время: O(n) - один проход по массиву
• Память: O(1) - используем только две переменные

Вариант с сохранением границ подмассива

Если нужно вернуть не только сумму, но и индексы подмассива:

def max_subarray_with_indices(nums: list[int]) -> tuple[int, int, int]:
    """Возвращает (max_sum, start_idx, end_idx)."""
    max_sum = nums[0]
    current_sum = nums[0]
    start = 0
    end = 0
    temp_start = 0  # Временная начальная позиция
    
    for i in range(1, len(nums)):
        # Если выгоднее начать заново
        if nums[i] > current_sum + nums[i]:
            current_sum = nums[i]
            temp_start = i  # Новое начало
        else:
            current_sum += nums[i]
        
        # Обновляем результат
        if current_sum > max_sum:
            max_sum = current_sum
            start = temp_start
            end = i
    
    return max_sum, start, end

# Пример
max_sum, start, end = max_subarray_with_indices([-2, 1, -3, 4, -1, 2, 1, -5, 4])
print(f"Максимальная сумма: {max_sum}")  # 6
print(f"Подмассив: {[-2, 1, -3, 4, -1, 2, 1, -5, 4][start:end+1]}")  # [4, -1, 2, 1]

Наивный подход O(n²) - неэффективно

def max_subarray_naive(nums: list[int]) -> int:
    """Простой перебор всех подмассивов."""
    max_sum = float('-inf')
    
    for i in range(len(nums)):
        current_sum = 0
        for j in range(i, len(nums)):
            current_sum += nums[j]
            max_sum = max(max_sum, current_sum)
    
    return max_sum

# Для массива из 100000 элементов:
# O(n²) = 10 млрд операций - медленно!
# O(n) = 100000 операций - мгновенно!

Тесты

def test_max_subarray():
    # Пример из задачи
    assert max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
    
    # Весь массив положительный
    assert max_subarray([1, 2, 3, 4]) == 10
    
    # Весь массив отрицательный
    assert max_subarray([-5, -2, -8, -1]) == -1
    
    # Один элемент
    assert max_subarray([42]) == 42
    
    # Смешанные
    assert max_subarray([5, -3, 5]) == 7
    assert max_subarray([-1, -2, -3]) == -1
    
    print("Все тесты пройдены!")

test_max_subarray()

Вариации задачи

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

def max_product_subarray(nums: list[int]) -> int:
    """Максимальное произведение вместо суммы."""
    if not nums:
        return 0
    
    # Нужно отслеживать и максимум, и минимум
    # Потому что отрицательное число может сделать минимум максимумом
    max_prod = nums[0]
    min_prod = nums[0]
    result = nums[0]
    
    for i in range(1, len(nums)):
        # Если число отрицательное, максимум и минимум меняются местами
        if nums[i] < 0:
            max_prod, min_prod = min_prod, max_prod
        
        max_prod = max(nums[i], max_prod * nums[i])
        min_prod = min(nums[i], min_prod * nums[i])
        
        result = max(result, max_prod)
    
    return result

Максимальная сумма циклического подмассива:

def max_subarray_circular(nums: list[int]) -> int:
    """Подмассив может обернуться вокруг массива."""
    # Случай 1: максимум не пересекает границу (обычный Кадане)
    max_kadane = max_subarray(nums)
    
    # Случай 2: максимум пересекает границу = total_sum - min_subarray
    total_sum = sum(nums)
    
    # Инвертируем числа и ищем минимум
    for i in range(len(nums)):
        nums[i] = -nums[i]
    
    min_kadane = max_subarray(nums)  # Это будет минимум исходного
    
    for i in range(len(nums)):
        nums[i] = -nums[i]
    
    max_circular = total_sum + min_kadane
    
    # Если все числа отрицательные, циклический результат неправильный
    if max_circular == 0:
        return max_kadane
    
    return max(max_kadane, max_circular)

Ключевые выводы

1. Алгоритм Кадане - O(n) решение вместо O(n²)
2. Инвариант: current_sum = максимум, заканчивающийся в i
3. Идея: Если текущая сумма отрицательна, начинаем заново
4. Частая ошибка: Забыть обновить max_sum = max(max_sum, current_sum)
5. На интервью: Сначала наивный O(n²), потом оптимизация до O(n)