Maximum Sum of Two Non-Overlapping Subarrays 两个非重叠子数组的最大和

问题描述：

问题 有一个整数数组nums，和2个整数firstlen，secondlen，要求找出2个非重叠子数组中的元素的最大和，长度分别是firstlen，secondlen。
不限制2个子数组的先后顺序。
firstlen，secondlen的范围[1,1000]
firstlen+secondlen的范围[2,1000]
firstlen，secondlen<=nums.length<=1000,
单个元素范围[0,1000]

分析

先不考虑数据范围的思考，使用暴力的方法来处理。
就是2个区间，假设是这2个区间和是 X,Y，根据题目的介绍一定存在这样的区间。但是无法确定的是2个位置，谁在前，谁在后。
所以2个情况都有可能，假设X前Y后，那么就需要确定X的位置，当X的位置确定后，那么X的右侧就是Y可能出现的位置，也就是说当X确定后，Y的取值决定与[Xend+1,n-1],Y要在这个区间内找到最大的。这样才可能与X+Y得到备选。
【先将nums进行前缀和预处理】
使用暴力的方法，每一轮计算Y的最大值，时间复杂度为ON，而枚举X的位置的次数也大概是ON，这样整体的时间复杂度就是ON*N，如果不使用前缀和，时间复杂度应该更高。
同样的 还要把Y前X后的计算一遍，整体来说，应该可以通过。

如果把问题再抽象一点，可以 利用滑动窗口，当窗口的右边界向右扩展，假设X前Y后，Y的位置就是紧靠窗口的右边界，那么Y的值就可以O1的时间复杂度计算，同时X的可用范围也在扩展，因为需要找到可用区间X的最大值，那么可以用前缀和，和DP记录目前X可以得到的最大值，时间复杂度O1。
窗口一直要滑到末尾，时间复杂度ON。
同样的思路Y前X后，也走一次。整体的时间复杂度ON，空间ON。
如果还要优化，DP计算X最大值部分可以使用变量计算，空间O1。

代码

时间复杂度 O(N ),空间复杂度 O(1)

class Solution {
    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 suml = 0;
        for (int i = 0; i < firstLen; ++i) {
            suml += nums[i];
        }
        int maxSumL = suml;
        int sumr = 0;
        for (int i = firstLen; i < firstLen + secondLen; ++i) {
            sumr += nums[i];
        }
        int res = maxSumL + sumr;
        for (int i = firstLen + secondLen, j = firstLen; i < nums.length; ++i, ++j) {
            suml += nums[j] - nums[j - firstLen];
            maxSumL = Math.max(maxSumL, suml);
            sumr += nums[i] - nums[i - secondLen];
            res = Math.max(res, maxSumL + sumr);
        }
        return res;
    }
}
 

public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int l = firstLen;
        int m = secondLen;
        int n = l+m;
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1];
        }
        int res = nums[l + m - 1];
        int Lmax = nums[l - 1];
        int Mmax = nums[m - 1];
        for (int i = l + m; i < nums.length; i++) {
            Lmax = Math.max(Lmax, nums[i - m] - nums[i - n]);
            Mmax = Math.max(Mmax, nums[i - l] - nums[i - n]);
            res = Math.max(res, Math.max(Lmax + nums[i] - nums[i - m],
            Mmax + nums[i] - nums[i - l]));
        }
        return res;
    }

Tag

动态规划 滑动窗口