Максимальная сумма различных подмассивов длины k

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

nums = [1, 5, 4, 2, 9, 9, 9], k = 3

15

nums = [4, 4, 4], k = 3

0

Решение

Здесь окно имеет фиксированную длину k, поэтому сумму можно обновлять так же, как в задаче о максимальном среднем подмассиве: добавляем новый элемент справа и убираем старый слева.

Но есть дополнительное условие: все элементы внутри окна должны быть различны. Чтобы проверять это быстро, будем хранить частоты элементов в текущем окне.

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

Поддерживаем два значения:

1. windowSum - сумма элементов текущего окна.
2. counts - частоты элементов текущего окна.

Когда окно достигает размера k, проверяем количество различных элементов. Если counts содержит ровно k ключей, значит, каждый элемент в окне встречается один раз. Тогда окно подходит, и можно обновить максимальную сумму.

После проверки сдвигаем окно: перед следующим шагом убираем элемент, который вышел за левую границу.

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

1. Инициализируем windowSum = 0, maxSum = 0 и таблицу частот.
2. Идем правой границей right по массиву.
3. Добавляем nums[right] в сумму и таблицу частот.
4. Если размер окна стал больше k, убираем элемент nums[right - k].
5. Когда окно имеет размер k и количество ключей в таблице равно k, обновляем maxSum.
6. Возвращаем maxSum.

Рассмотрим пример:

nums = [1, 5, 4, 2, 9, 9, 9], k = 3

1. Окно [1, 5, 4], сумма равна 10, все элементы различны.

2. Окно [5, 4, 2], сумма равна 11, все элементы различны.

3. Окно [4, 2, 9], сумма равна 15, все элементы различны. Это текущий максимум.

4. Окно [2, 9, 9], есть повтор 9.

5. Окно [9, 9, 9], есть повтор 9.

Окна с повторами не подходят. Максимальная сумма среди валидных окон равна 15.

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

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

Мы один раз проходим по массиву. Добавление и удаление элемента из хеш-таблицы в среднем занимают O(1).

Итоговая временная сложность: O(n).

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

В таблице частот хранится не больше k элементов текущего окна.

Пространственная сложность: O(k).

Код решения

Приведем код решения.

func maximumSubarraySum(nums []int, k int) int64 {
    counts := map[int]int{}
    var windowSum int64
    var maxSum int64
 
    for right := 0; right < len(nums); right++ {
        windowSum += int64(nums[right])
        counts[nums[right]]++
 
        if right >= k {
            leftValue := nums[right-k]
            windowSum -= int64(leftValue)
            counts[leftValue]--
            if counts[leftValue] == 0 {
                delete(counts, leftValue)
            }
        }
 
        if right >= k-1 && len(counts) == k {
            maxSum = max(maxSum, windowSum)
        }
    }
 
    return maxSum
}

Итоги

Задача Maximum Sum of Distinct Subarrays With Length K объединяет фиксированное скользящее окно и проверку уникальности через частоты.

1. Суть алгоритма: поддерживаем сумму окна длины k и таблицу частот; если количество различных элементов равно k, обновляем максимальную сумму.
2. Эффективность:
   • Временная сложность: O(n), потому что каждый элемент один раз добавляется в окно и один раз удаляется из него.
   • Пространственная сложность: O(k), так как в таблице хранятся элементы текущего окна.
3. Граничные случаи:
   • Подходящего окна нет: maxSum останется 0.
   • k == 1: любой одиночный элемент уникален, ответом будет максимальный элемент массива.
   • В окне есть повтор: количество различных элементов меньше k, поэтому окно не учитывается.
4. Оптимальное решение: мы не пересчитываем сумму и уникальность каждого окна с нуля, а обновляем оба состояния при каждом сдвиге.