1031. Maximum Sum of Two Non-Overlapping Subarrays

LeetCode medium original: C# #array #csharp #graph #leetcode #math #medium #prefix-sum #search

選択した UI 言語に合わせて問題文をロシア語から翻訳します。コードは変更しません。

LeetCode Static

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

例:

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

Output: 20

C# 解法

照合済み/オリジナル

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++ 解法

自動ドラフト、提出前に確認

#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 解法

照合済み/オリジナル

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 解法

照合済み/オリジナル

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 解法

照合済み/オリジナル

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 解法

照合済み/オリジナル

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
}

Algorithm

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

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

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

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

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

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

😎

Vacancies for this task

有効な求人 with overlapping task tags are 表示.

すべての求人

有効な求人はまだありません。