Задача: 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 {
    func maxSumTwoNoOverlap(_ nums: [Int], _ firstLen: Int, _ secondLen: Int) -> Int {
        func maxSumNonOverlap(_ nums: [Int], _ firstLen: Int, _ secondLen: Int) -> Int {
            let n = nums.count
            var prefix = [Int](repeating: 0, count: n + 1)
            for i in 0..<n {
                prefix[i + 1] = prefix[i] + nums[i]
            }
            
            var maxFirst = [Int](repeating: 0, count: n)
            for i in firstLen - 1..<n {
                maxFirst[i] = max((i > 0 ? maxFirst[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - firstLen])
            }
            
            var maxSecond = [Int](repeating: 0, count: n)
            for i in secondLen - 1..<n {
                maxSecond[i] = max((i > 0 ? maxSecond[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - secondLen])
            }
            
            var maxSum = 0
            for i in firstLen + secondLen - 1..<n {
                maxSum = max(maxSum, maxFirst[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]))
            }
            
            return maxSum
        }
        
        return max(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(nums.reversed(), secondLen, firstLen))
    }
}

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