PythonTalk

🃏 Разбор карточной задачки: от O(k²) к O(k)!

Пришло время разобрать нашу задачу про карточный турнир.

🤔 Распространённый подход: полный перебор

Самая очевидная стратегия — перебрать все возможные комбинации взятых карт. Мы можем взять:
- k карт слева, 0 справа
- k-1 карт слева, 1 справа
- k-2 карт слева, 2 справа
- ...
- 0 карт слева, k карт справа

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

def max_score_slow(card_points, k):
    max_sum = 0
    n = len(card_points)

    for i in range(k + 1):
        # i - сколько карт берем справа
        # k-i - сколько карт берем слева
        left_sum = sum(card_points[:k - i])
        right_sum = sum(card_points[n - i:])
        max_sum = max(max_sum, left_sum + right_sum)

    return max_sum

Главный минус здесь — многократный вызов sum() внутри цикла. Каждая такая операция сама по себе занимает время, пропорциональное количеству элементов. В итоге общая сложность алгоритма получается O(k²), что может быть медленно на больших данных.

А можно ли быстрее? Конечно!

🚀 Эталонное решение: Скользящее окно за O(k)

Вместо того чтобы каждый раз пересчитывать сумму с нуля, мы можем вычислить её один раз, а затем "сдвигать" наш выбор, обновляя сумму за константное время O(1).

Как это работает?
1. Сначала считаем, что мы взяли первые k карт слева. Это наша первоначальная max_sum.
2. Затем в цикле k раз делаем "обмен": убираем одну карту с конца левой группы и добавляем одну карту справа.
3. На каждом шаге обновляем текущую сумму и сравниваем её с максимальной.

def max_score_fast(card_points, k):
    n = len(card_points)
    
    current_sum = sum(card_points[:k])
    max_sum = current_sum

    for i in range(1, k + 1):
        # Обновляем сумму за O(1):
        # отнимаем крайний левый элемент и прибавляем крайний правый
        current_sum = current_sum - card_points[k - i] + card_points[n - i]
        max_sum = max(max_sum, current_sum)
            
    return max_sum

⏳ Время: O(k). Один начальный подсчет суммы sum(card_points[:k]) занимает O(k), и цикл также выполняется k раз с операциями за O(1).
💾 Память: O(1). Мы храним всего несколько переменных.

💡 Красивая альтернатива: инверсия задачи

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

Вместо того чтобы максимизировать сумму k карт, которые мы берём, давайте минимизируем сумму n-k карт в центре, которые мы оставляем на столе.

Задача превращается в "найти непрерывный подмассив длиной n-k с минимальной суммой". Это тоже классическая задача на скользящее окно!

def max_score_inverted(card_points, k):
    n = len(card_points)
    window_size = n - k
    
    total_sum = sum(card_points)
    
    if window_size <= 0:
        return total_sum

    min_subarray_sum = current_sum = sum(card_points[:window_size])

    for i in range(window_size, n):
        current_sum += card_points[i] - card_points[i - window_size]
        min_subarray_sum = min(min_subarray_sum, current_sum)
            
    return total_sum - min_subarray_sum

Этот подход имеет сложность O(N), что тоже отлично. Он особенно хорош, когда k близко к N.

#алгособес