Сложность: 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:
def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
def maxSumNonOverlap(nums, firstLen, secondLen):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
max_first = [0] * n
for i in range(firstLen - 1, n):
max_first[i] = max(max_first[i - 1], prefix[i + 1] - prefix[i + 1 - firstLen])
max_second = [0] * n
for i in range(secondLen - 1, n):
max_second[i] = max(max_second[i - 1], prefix[i + 1] - prefix[i + 1 - secondLen])
max_sum = 0
for i in range(firstLen + secondLen - 1, n):
max_sum = max(max_sum, max_first[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]))
return max_sum
return max(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(nums[::-1], secondLen, firstLen))
Ставь 👍 и забирай 📚 Базу знаний