LeetCode 1031. Maximum sum of two non overlapping subarrays

Problem description

Give an array of nonnegative integers A , Return two non overlapping （ continuity ） The maximum sum of elements in a subarray , The length of the subarray is L and M.（ What needs to be clarified here is , Long for L The subarray of can appear at length as M Before or after the subarray of .）

In form , Return to the biggest V, and V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) And meet one of the following conditions ：

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

Example 1：

Input ：A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2
Output ：20
explain ： In a selection of subarrays ,[9] The length is 1,[6,5] The length is 2.
Example 2：

Input ：A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
Output ：29
explain ： In a selection of subarrays ,[3,8,1] The length is 3,[8,9] The length is 2.
Example 3：

Input ：A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3
Output ：31
explain ： In a selection of subarrays ,[5,6,0,9] The length is 4,[0,3,8] The length is 3.
 

Tips ：

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

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/maximum-sum-of-two-non-overlapping-subarrays
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

java

class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int n = nums.length;
        // The prefix and 
        int[] sum = new int[n + 1];
        for(int i = 0;i < n;i++){
            sum[i + 1] = sum[i] + nums[i];
        }
        // In exchange for 
        if(firstLen > secondLen){
            firstLen ^= secondLen;
            secondLen ^= firstLen;
            firstLen ^= secondLen;
        }
        int[][] dp = new int[n + 1][2];
        int ans = 0;
        // From firstLen Start 
        for(int i = firstLen;i <= n;i++){
            // The current element has been closed before firstLen And 
            int s1 = sum[i] - sum[i - firstLen];
            dp[i][0] = Math.max(dp[i - 1][0],s1);
            ans = Math.max(ans,s1 + dp[i - firstLen][1]);
            if(i >= secondLen){
                int s2 = sum[i] - sum[i - secondLen];
                dp[i][1] = Math.max(dp[i - 1][1],s2);
                ans = Math.max(ans,s2 + dp[i - secondLen][0]);
            }
        }
        return ans;
    }
}