【算法】Maximum Sum of Two Non-Overlapping Subarrays 两个非重叠子数组的最大和-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】Maximum Sum of Two Non-Overlapping Subarrays 两个非重叠子数组的最大和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

问题描述：

问题有一个整数数组nums，和2个整数firstlen，secondlen，要求找出2个非重叠子数组中的元素的最大和，长度分别是firstlen，secondlen。
不限制2个子数组的先后顺序。
firstlen，secondlen的范围 $[1, 1000]$
firstlen+secondlen的范围 $[2, 1000]$
$f i rs tl e n ， seco n d l e n <= n u m s . l e n g t h <= 1000$ ,
单个元素范围 $[0, 1000]$

分析

先不考虑数据范围的思考，使用暴力的方法来处理。

就是2个区间，假设是这2个区间和是 X,Y，根据题目的介绍一定存在这样的区间。但是无法确定的是2个位置，谁在前，谁在后。
所以2个情况都有可能，假设X前Y后，那么就需要确定X的位置，当X的位置确定后，那么X的右侧就是Y可能出现的位置，也就是说当X确定后，Y的取值决定与 $[X e n d + 1, n - 1]$ ,Y要在这个区间内找到最大的。这样才可能与 $X + Y$ 得到备选。

【先将nums进行前缀和预处理】

使用暴力的方法，每一轮计算Y的最大值，时间复杂度为 $O (N)$ ，而枚举X的位置的次数也大概是ON，这样整体的时间复杂度就是 $O(N^2 )$ ，如果不使用前缀和，时间复杂度应该更高。
同样的还要把Y前X后的计算一遍，整体来说，应该可以通过。

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

代码

时间复杂度 $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;
    }