关于算法复杂度:每日一题两个非重叠子数组的最大和

1031. 两个非重叠子数组的最大和

关键词：前缀和

题目起源：1031. 两个非重叠子数组的最大和 – 力扣（Leetcode）

题目形容

 T 前缀和

给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，请你找出并返回两个非重叠 子数组 中元素的最大和， 长度别离为 firstLen 和 secondLen。

长度为 firstLen 的子数组能够呈现在长为 secondLen 的子数组之前或之后，但二者必须是不重叠的。

子数组是数组的一个 间断 局部。

输出：nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
输入：20
解释：子数组的一种抉择中，[9] 长度为 1，[6,5] 长度为 2。

输出：nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
输入：29
解释：子数组的一种抉择中，[3,8,1] 长度为 3，[8,9] 长度为 2。

输出：nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3
输入：31
解释：子数组的一种抉择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。

数据范畴
1 <= firstLen, secondLen <= 1000
2 <= firstLen + secondLen <= 1000
firstLen + secondLen <= nums.length <= 1000
0 <= nums[i] <= 1000

问题剖析

两个不重叠子数组必然位于某条分界线的两侧，于是，无妨枚举每条分界线，设其左侧子数组的最大值为 l，右侧子数组的最大值为 r，则，max{l+r}即为答案。

如何疾速晓得分界线左 / 右侧的最大值呢？无妨先思考长度为 firstLen 的子数组能够呈现在长为 secondLen 的子数组之前的状况。因为子数组长度已知，且子数组间断，于是可采纳一遍扫描，窗口一直向右 / 左滑动，预处理出所有分界线左 / 右侧的子数组的最大值。

当长度为 firstLen 的子数组在之后时，求解过程完全相同，于是，无妨上述求解过程封装成一个函数，将前后数组的长度作为参数。

为了不便计算指定区间元素和，可先预处理出前缀和。

工夫复杂度：O(n)

空间复杂度：O(n)

代码实现

int maxSumTwoNoOverlap_2(vector<int> &nums, int firstLen, int secondLen) {// pre[i]示意 [1..i] 中指定长度的子数组的最大值
    int n = nums.size(), pre[n+1];
    // 前缀和
    for (int i = 1; i < n; i++)nums[i] += nums[i - 1];
    // 抽取公共局部
    auto f = [&](int s, int t) {
        int res = 0;
        // [1..i]中长度为 s 的子数组的最大值
        pre[s] = nums[s - 1];
        for (int i = s + 1; i <= n; i++)
            pre[i] = max(nums[i - 1] - nums[i - 1 - s], pre[i - 1]);
        // [i+1..n]中长度为 t 的子数组的最大值
        for (int i = n - t, curMax = 0; i >= s; i--) {curMax = max(nums[i + t - 1] - nums[i - 1], curMax);
            res = max(pre[i] + curMax, res);
        }
        return res;
    };
    return max(f(firstLen, secondLen), f(secondLen, firstLen));
}