乐趣区

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

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

关键词:前缀和

题目起源:1031. 两个非重叠子数组的最大和 – 力扣(Leetcode)

题目形容

 T 前缀和

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

长度为 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));
}
退出移动版