1031. 两个非重叠子数组的最大和 - Java 动态规划+前缀和

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

题解

设DP[i]是子问题：数组[0,i]中两个非重叠子数组的最大和

我们先考虑一些数据的预处理：

考虑到要计算元素和，我们可以用一个前缀和数组prefix来快速计算，设prefix[i]是数组[0,i]的前缀和，那么有

对于以i结尾的子数组1，其元素和为：prefix[i]-prefix[i-firstLen])
对于以i结尾的子数组2，其元素和为：prefix[i]-prefix[i-secondLen])

for(int i=0;i<nums.length;i++){
    if(i==0)prefix[i]=nums[i];
    else prefix[i]=prefix[i-1]+nums[i];
}

边界情况：当子数组恰好以nums[0]起始时，应当直接等于prefix[i]

与此同时，我们还可以维护一个max数组，max数组记录下子数组在[0,i]中的最大元素和，对于max[i]而言有两种情况：

子数组以i结尾，则此时子数组元素和为prefix[i]-prefix[i-firstLen])
子数组不以i结尾，则此时子数组的最大元素和仍为max[i-1]，二者比较取最大值即为max[i]
边界情况1：索引下标应当直接从len-1开始算起，因为在那之前数组长度无法容纳下子数组
边界情况2：当子数组恰好以nums[0]起始时，max[i]应当直接等于prefix[i]

for(int i=len-1;i<nums.length;i++){
    max[i]=i+1==len?prefix[i]:Math.max(max[i-1],prefix[i]-prefix[i-len]);
}

此时我们再回过来考虑DP，当遍历从DP[i-1]推进到DP[i]时，我们考虑三种情况：

子数组1以i结尾，则此时子数组1占据了[i-firstLen+1,i]的位置，那么子数组2的位置只能从[0,i-firstLen]中寻找位置
- 此时dp[i]的最优解为子数组1的元素和+子数组2在[0,i-firstLen]中的最大元素和

子数组2以i结尾，则此时子数组2占据了[i-secondLen+1,i]的位置，那么子数组1的位置只能从[0,i-secondLen]中寻找位置
- 此时dp[i]的最优解为子数组2的元素和+子数组2在[0,i-secondLen]中的最大元素和

子数组1和2均不以i结尾，此时的遍历无意义

以上三种情况取最大值即为DP[i]的取值，即：

考虑到i只有在大于等于firstLen+secondLen-1时数组长度才能同时容纳下两个子数组，i可以直接从firstLen+secondLen-1开始遍历

for(int i=firstLen+secondLen-1;i<nums.length;i++){
    dp[i]=Math.max(max[i-firstLen][1]+(prefix[i]-prefix[i-firstLen]),max[i-secondLen][0]+(prefix[i]-prefix[i-secondLen]));
    dp[i]=Math.max(dp[i],dp[i-1]);
}

我们可以看出，dp[i]实际上只与dp[i-1]挂钩，所以可以省去这个数组，直接用一个变量滚动即可，即

for(int i=firstLen+secondLen-1;i<nums.length;i++){
    tmp=Math.max(
        max[i-firstLen][1]+(prefix[i]-prefix[i-firstLen]),
        max[i-secondLen][0]+(prefix[i]-prefix[i-secondLen]));
    maxsum=Math.max(maxsum,tmp);
}

将几个循环合并在一起，就有了我们最终的结果

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {	
        int[] prefix=new int[nums.length];
        int[][] max=new int[nums.length][2];
        int maxsum=0,tmp;

        for(int i=0;i<nums.length;i++){
            if(i==0)prefix[i]=nums[i];
            else prefix[i]=prefix[i-1]+nums[i];
        }
        for(int i=firstLen-1;i<nums.length;i++){
            max[i][0]=i+1==firstLen?prefix[i]:Math.max(max[i-1][0],prefix[i]-prefix[i-firstLen]);
        }
        for(int i=secondLen-1;i<nums.length;i++){
            max[i][1]=i+1==secondLen?prefix[i]:Math.max(max[i-1][1],prefix[i]-prefix[i-secondLen]);
        }
        for(int i=firstLen+secondLen-1;i<nums.length;i++){
            tmp=Math.max(
                max[i-firstLen][1]+(prefix[i]-prefix[i-firstLen]),
                max[i-secondLen][0]+(prefix[i]-prefix[i-secondLen]));
            maxsum=Math.max(maxsum,tmp);
        }
        return maxsum;
    }
}