原文链接: https://leetcode-cn.com/problems/maximum-sum-of-two-non-overlapping-subarrays

英文原文

Given an integer array nums and two integers firstLen and secondLen, return the maximum sum of elements in two non-overlapping subarrays with lengths firstLen and secondLen.

The array with length firstLen could occur before or after the array with length secondLen, but they have to be non-overlapping.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20
Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.

Example 2:

Input: nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
Output: 29
Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.

Example 3:

Input: nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3
Output: 31
Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [3,8] with length 3.

 

Constraints:

• 1 <= firstLen, secondLen <= 1000
• 2 <= firstLen + secondLen <= 1000
• firstLen + secondLen <= nums.length <= 1000
• 0 <= nums[i] <= 1000

中文题目

给出非负整数数组 A ，返回两个非重叠（连续）子数组中元素的最大和，子数组的长度分别为 L 和 M。（这里需要澄清的是，长为 L 的子数组可以出现在长为 M 的子数组之前或之后。）

从形式上看，返回最大的 V，而 V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) 并满足下列条件之一：

 

• 0 <= i < i + L - 1 < j < j + M - 1 < A.length, 或
• 0 <= j < j + M - 1 < i < i + L - 1 < A.length.

 

示例 1：

输入：A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2
输出：20
解释：子数组的一种选择中，[9] 长度为 1，[6,5] 长度为 2。

示例 2：

输入：A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
输出：29
解释：子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。

示例 3：

输入：A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3
输出：31
解释：子数组的一种选择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。

 

提示：

1. L >= 1
2. M >= 1
3. L + M <= A.length <= 1000
4. 0 <= A[i] <= 1000

通过代码

高赞题解

这道题原来在英文版Leetcode上刷到过，当时记得最优办法非常精炼，这次在评论区里也没有找到有人写类似方法，于是复制粘贴过来。原作者是lee215,
https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/discuss/278251/JavaC%2B%2BPython-O(N)Time-O(1)-Space

只贴一下C++的：

int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
    for (int i = 1; i < A.size(); ++i)
        A[i] += A[i - 1];
    int res = A[L + M - 1], Lmax = A[L - 1], Mmax = A[M - 1];
    for (int i = L + M; i < A.size(); ++i) {
        Lmax = max(Lmax, A[i - M] - A[i - L - M]);
        Mmax = max(Mmax, A[i - L] - A[i - L - M]);
        res = max(res, max(Lmax + A[i] - A[i - M], Mmax + A[i] - A[i - L]));
    }
    return res;
}

统计信息

通过次数	提交次数	AC比率
5176	9046	57.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言