Java | LeetCode
Задача: 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. Найдите максимальную сумму для каждого случая.
😎 Решение:
public class Solution {
public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
return Math.max(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(reverse(nums), secondLen, firstLen));
}
private int maxSumNonOverlap(int[] nums, int firstLen, int secondLen) {
int n = nums.length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; ++i) {
prefix[i + 1] = prefix[i] + nums[i];
}
int[] maxFirst = new int[n];
for (int i = firstLen - 1; i < n; ++i) {
maxFirst[i] = Math.max((i > 0 ? maxFirst[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - firstLen]);
}
int[] maxSecond = new int[n];
for (int i = secondLen - 1; i < n; ++i) {
maxSecond[i] = Math.max((i > 0 ? maxSecond[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - secondLen]);
}
int maxSum = 0;
for (int i = firstLen + secondLen - 1; i < n; ++i) {
maxSum = Math.max(maxSum, maxFirst[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]));
}
return maxSum;
}
private int[] reverse(int[] nums) {
int n = nums.length;
int[] reversed = new int[n];
for (int i = 0; i < n; ++i) {
reversed[i] = nums[n - i - 1];
}
return reversed;
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 416 ·