1031. Maximum Sum of Two Non-Overlapping Subarrays 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int[] prefixSums = new int[nums.length + 1];
        for (int i = 1; i < prefixSums.length; i++) {
            prefixSums[i] = prefixSums[i - 1] + nums[i - 1];
        }

        return Math.max(maxSum(prefixSums, firstLen, secondLen), maxSum(prefixSums, secondLen, firstLen));
    }

    private int maxSum(int[] prefixSums, int firstLen, int secondLen) {
        int maxFirstSum = 0;
        int maxSum = 0;

        // 枚举 second 数组的右端点，可知：first 数组的和为 prefixSums[i - secondLen] - prefixSums[i - secondLen - firstLen], second 数组的和为 prefixSums[i] - prefixSums[i - secondLen]
        for (int i = firstLen + secondLen; i < prefixSums.length; i++) {
            // 每次移动 second 数组时，尝试更新 first 数组的最大值
            maxFirstSum = Math.max(maxFirstSum, prefixSums[i - secondLen] - prefixSums[i - secondLen - firstLen]);
            maxSum = Math.max(maxSum, maxFirstSum + prefixSums[i] - prefixSums[i - secondLen]);
        }

        return maxSum;
    }
}

References

1031. Maximum Sum of Two Non-Overlapping Subarrays