题目地址：https://leetcode.cn/problems/maximum-sum-of-two-non-overlapping-subarrays/description/

我的思路

实现比较麻烦，计算复杂

  1. 先计算出 firstLen 长度的最大和的子集，再从剩余的数组中计算 secondLen 长度的最大和的子集 ，然后相加
  2. 再计算出 secondLen 长度的最大和的子集，再从剩余的数组中计算 firstLen 长度的最大和的子集 ，然后相加
  3. 比较两个结果，取最大值

官方思路

动态规划 + 滑动窗口

首先题目给出一个长度为 n 的数组 nums。现在我们需要返回两个长度分别为 firstLen 和 secondLen 的非重叠的子数组的最大和，firstLen+secondLen≤n，其中这两段子数组的前后顺序没有要求。

由于两段子数组的前后顺序没有区别，所以现在不妨设长度为 firstLen 的子数组在长度为 secondLen 的子数组前来计算此时的两段子数组的最大和。首先我们用 nums[i,j] 来表示 nums[i],nums[i+1],…,nums[j−1] 这一段子数组，并记 sum(nums[l,r]) 表示子数组 nums[l,r] 的和，dp[i] 为 nums[0,i+1] 中长度为 firstLen 的最大子数组和，若不存在长度为 firstLen 的子数组则为 0。那么对于某一段长度为 secondLen 的子数组 nums[j,j+secondLen]，0≤j<j+secondLen≤n，所以此时的两个数组的最大和为

dp[j−1]+sum(nums[j,j+secondLen])

又因为

dp[i]=max{dp[i−1],sum(nums[i+1−firstLen,i+1])}

由于现在长度为 secondLen 在长度为 firstLen 的后面，所以用两个大小为 firstLen 和 secondLen 的滑动窗口分别从位置 0 和 firstLen 同时开始从左往右滑动，并在过程中维护窗口中的和。因为对于 ∀i<firstLen−1，有 dp[i]=0，并当 i=firstLen−1 时为初始第一个窗口的和。那么在两个窗口从左到右移动的过程中，通过移动第一个窗口来更新 dp 值，通过第二个窗口来计算此时的最大和，并记录移动过程中的最大值即可。

同理我们可以得到当 secondLen 的子数组在长度为 firstLen 的子数组前时，两段子数组的最大和，两种情况取较大值即为最终的答案。由于 dp[i] 的求解只与 dp[i−1] 有关，所以在实现的过程中我们可以通过「滚动数组」来进行空间优化。

题解代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {  
    return Math.max(help(nums, firstLen, secondLen), help(nums, secondLen, firstLen));  
}  
  
public int help(int[] nums, int firstLen, int secondLen) {  
    int lSum = 0;  
    for (int i = 0; i < firstLen; i++) {  
        lSum += nums[i];  
    }  
    int rSum = 0;  
    for (int i = firstLen; i < firstLen + secondLen; i++) {  
        rSum += nums[i];  
    }  
    int res = lSum + rSum;  
    int lMaxSum = lSum;  
    for (int i = firstLen + secondLen, j = firstLen; i < nums.length; ++i, ++j) {    
	    // 这里必须使用lSum存，因为是移动窗口，前面加一个元素，就必须是在连续的位置上减一个元素
        lSum = lSum + nums[j] - nums[j - firstLen];  
        lMaxSum = Math.max(lMaxSum, lSum);  
        rSum = rSum + nums[i] - nums[i - secondLen];  
        res = Math.max(res, lMaxSum + rSum);  
    }  
    return res;  
}