Задача: 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 {
    fun maxSumTwoNoOverlap(nums: IntArray, firstLen: Int, secondLen: Int): Int {
        fun maxSumNonOverlap(nums: IntArray, firstLen: Int, secondLen: Int): Int {
            val n = nums.size
            val prefix = IntArray(n + 1)
            for (i in 0 until n) {
                prefix[i + 1] = prefix[i] + nums[i]
            }
            
            val maxFirst = IntArray(n)
            for (i in firstLen - 1 until n) {
                maxFirst[i] = maxOf(if (i > 0) maxFirst[i - 1] else 0, prefix[i + 1] - prefix[i + 1 - firstLen])
            }
            
            val maxSecond = IntArray(n)
            for (i in secondLen - 1 until n) {
                maxSecond[i] = maxOf(if (i > 0) maxSecond[i - 1] else 0, prefix[i + 1] - prefix[i + 1 - secondLen])
            }
            
            var maxSum = 0
            for (i in firstLen + secondLen - 1 until n) {
                maxSum = maxOf(maxSum, maxFirst[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]))
            }
            
            return maxSum
        }
        
        return maxOf(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(nums.reversedArray(), secondLen, firstLen))
    }
}

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