Задача: 1031. Maximum Sum of Two Non-Overlapping Subarrays
Сложность: medium

Если задан целочисленный массив nums и два целых числа firstLen и secondLen, верните максимальную сумму элементов в двух непересекающихся подмассивах с длинами firstLen и secondLen. Массив с длиной firstLen может находиться до или после массива с длиной secondLen, но они должны быть непересекающимися. Подмассив - это смежная часть массива.

Пример:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20

👨‍💻 Алгоритм:

1⃣Предварительные вычисления:
Вычислите сумму всех подмассивов длины firstLen и secondLen и сохраните их в списках.

2⃣Поиск максимальной суммы:
Переберите все возможные позиции для подмассива длины firstLen и для каждого такого подмассива найдите максимальную сумму для подмассива длины secondLen, который не пересекается с текущим подмассивом длины firstLen.

3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.

😎 Решение:

class Solution {
    function maxSumTwoNoOverlap($nums, $firstLen, $secondLen) {
        return max($this->maxSumNonOverlap($nums, $firstLen, $secondLen), $this->maxSumNonOverlap(array_reverse($nums), $secondLen, $firstLen));
    }
    
    private function maxSumNonOverlap($nums, $firstLen, $secondLen) {
        $n = count($nums);
        $prefix = array_fill(0, $n + 1, 0);
        for ($i = 0; $i < $n; $i++) {
            $prefix[$i + 1] = $prefix[$i] + $nums[$i];
        }
        
        $maxFirst = array_fill(0, $n, 0);
        for ($i = $firstLen - 1; $i < $n; $i++) {
            $maxFirst[$i] = max(($i > 0 ? $maxFirst[$i - 1] : 0), $prefix[$i + 1] - $prefix[$i + 1 - $firstLen]);
        }
        
        $maxSecond = array_fill(0, $n, 0);
        for ($i = $secondLen - 1; $i < $n; $i++) {
            $maxSecond[$i] = max(($i > 0 ? $maxSecond[$i - 1] : 0), $prefix[$i + 1] - $prefix[$i + 1 - $secondLen]);
        }
        
        $maxSum = 0;
        for ($i = $firstLen + $secondLen - 1; $i < $n; $i++) {
            $maxSum = max($maxSum, $maxFirst[$i - $secondLen] + ($prefix[$i + 1] - $prefix[$i + 1 - $secondLen]));
        }
        
        return $maxSum;
    }
}

Ставь 👍 и забирай 📚 Базу знаний