← Static tasks

1031. Maximum Sum of Two Non-Overlapping Subarrays

leetcode medium

#array#csharp#graph#leetcode#math#medium#prefix-sum#search

Task

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

Пример:

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

Output: 20

C# solution

matched/original
public class Solution {
    public int MaxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        return Math.Max(MaxSumNonOverlap(nums, firstLen, secondLen), MaxSumNonOverlap(nums.Reverse().ToArray(), 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;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        return max(MaxSumNonOverlap(nums, firstLen, secondLen), MaxSumNonOverlap(nums.Reverse().ToArray(), secondLen, firstLen));
    }
    
    private int MaxSumNonOverlap(vector<int>& nums, int firstLen, int secondLen) {
        int n = nums.size();
        vector<int>& prefix = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        vector<int>& maxFirst = new int[n];
        for (int i = firstLen - 1; i < n; ++i) {
            maxFirst[i] = max((i > 0 ? maxFirst[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - firstLen]);
        }
        
        vector<int>& maxSecond = new int[n];
        for (int i = secondLen - 1; i < n; ++i) {
            maxSecond[i] = 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 = max(maxSum, maxFirst[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]));
        }
        
        return maxSum;
    }
}

Java solution

matched/original
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;
    }
}

JavaScript solution

matched/original
var maxSumTwoNoOverlap = function(nums, firstLen, secondLen) {
    return Math.max(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(nums.reverse(), secondLen, firstLen));
};

function maxSumNonOverlap(nums, firstLen, secondLen) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    
    const maxFirst = new Array(n).fill(0);
    for (let i = firstLen - 1; i < n; i++) {
        maxFirst[i] = Math.max((i > 0 ? maxFirst[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - firstLen]);
    }
    
    const maxSecond = new Array(n).fill(0);
    for (let i = secondLen - 1; i < n; i++) {
        maxSecond[i] = Math.max((i > 0 ? maxSecond[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - secondLen]);
    }
    
    let maxSum = 0;
    for (let i = firstLen + secondLen - 1; i < n; i++) {
        maxSum = Math.max(maxSum, maxFirst[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]));
    }
    
    return maxSum;
}

Python solution

matched/original
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))

Go solution

matched/original
func maxSumTwoNoOverlap(nums []int, firstLen int, secondLen int) int {
    return max(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(reverse(nums), secondLen, firstLen))
}

func maxSumNonOverlap(nums []int, firstLen int, secondLen int) int {
    n := len(nums)
    prefix := make([]int, n + 1)
    for i := 0; i < n; i++ {
        prefix[i + 1] = prefix[i] + nums[i]
    }
    
    maxFirst := make([]int, n)
    for i := firstLen - 1; i < n; i++ {
        maxFirst[i] = max(if i > 0 { maxFirst[i - 1] } else { 0 }, prefix[i + 1] - prefix[i + 1 - firstLen])
    }
    
    maxSecond := make([]int, n)
    for i := secondLen - 1; i < n; i++ {
        maxSecond[i] = max(if i > 0 { maxSecond[i - 1] } else { 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
}

func reverse(nums []int) []int {
    n := len(nums)
    reversed := make([]int, n)
    for i := 0; i < n; i++ {
        reversed[i] = nums[n - i - 1]
    }
    return reversed
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

Предварительные вычисления:

Вычислите сумму всех подмассивов длины firstLen и secondLen и сохраните их в списках.

Поиск максимальной суммы:

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

Сравнение двух случаев:

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

😎