▲

3

▼

🔥 Модифицированный алгоритм Кадане для подмассивов с длиной, кратной k

leetcoder, 13-12-2024 , 165

Очередная наша задача - 3381. Maximum Subarray Sum With Length Divisible by K

Описание задачи

Дано целое число k и массив чисел nums. Необходимо найти максимальную сумму подмассива, длина которого кратна k.

🚀 Идея

Данная задача расширяет классический алгоритм нахождения максимальной суммы подмассива (алгоритм Кадане) для случаев, когда длина подмассива должна быть кратной k. Чтобы учесть это условие, мы перебираем все смещения в полуинтервале [0,k) и анализируем подмассивы с шагом k.

🔍 Подход

1. Префиксные суммы:
   • Вычисляем массив префиксных сумм, чтобы быстро находить сумму любого подмассива.
2. Перебор смещений:
   • Итерируем по всем возможным начальным смещениям [0,k), чтобы обрабатывать подмассивы длиной, кратной k.
3. Модификация алгоритма Кадане:
   • Для каждого смещения применяем алгоритм нахождения максимальной суммы подмассива.
   • Если текущая сумма становится отрицательной, начинаем новый расчет с текущей позиции (сброс индекса начала подмассива).

⏱️ Ассимптотика

• Временная сложность:
  • На вычисление префиксных сумм требуется O(n).
  • Основной цикл: внешний цикл выполняется O(k), а внутренний — O(n/k), что в сумме дает O(k)×O(n/k)=O(n).
  • Итоговая сложность: O(n).
• Пространственная сложность:
  • O(n) для хранения префиксных сумм.

Исходный код решения

impl Solution {
    pub fn max_subarray_sum(nums: Vec<i32>, k: i32) -> i64 {
        let n = nums.len();
        let k = k as usize;

        // Compute prefix sums
        let mut prefix_sums = vec![0i64; n + 1];
        for i in 0..n {
            prefix_sums[i + 1] = prefix_sums[i] + nums[i] as i64;
        }

        let mut best = i64::MIN;

        // Iterate over each offset
        for offset in 0..k {
            let mut start = offset;
            for end in (offset + k..=n).step_by(k) {
                // Calculate the subarray sum
                let subarray_sum = prefix_sums[end] - prefix_sums[start];
                // Update the best result
                best = best.max(subarray_sum);
                // Reset start if the current sum is negative
                if subarray_sum < 0 {
                    start = end;
                }
            }
        }

        best
    }
}