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

链接：1031.两个非重叠子数组的最大和
难度：Medium
标签：数组、动态规划、滑动窗口
简介：给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，请你找出并返回两个非重叠 子数组 中元素的最大和，长度分别为 firstLen 和 secondLen 。

题解 1 - cpp

• 编辑时间：2022-01-14
• 执行用时：4ms
• 内存消耗：8.1MB
• 编程语言：cpp
• 解法介绍：分别计算左右。

class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        int n = nums.size(), lmax[n + 1], mmax[n + 1];
        memset(lmax, 0, sizeof(lmax));
        memset(mmax, 0, sizeof(mmax));
        for (int i = n - 1, lsum = 0, msum = 0; i >= 0; i--) {
            lsum += nums[i];
            msum += nums[i];
            if (i + firstLen < n) lsum -= nums[i + firstLen];
            if (i + secondLen < n) msum -= nums[i + secondLen];
            if (i + firstLen <= n) lmax[i] = max(lmax[i + 1], lsum); 
            if (i + secondLen <= n) mmax[i] = max(mmax[i + 1], msum); 
        }
        int ans = 0;
        for (int i = 0, lsum = 0, msum = 0; i < n; i++) {
            lsum += nums[i];
            msum += nums[i];
            if (i >= firstLen) lsum -= nums[i - firstLen];
            if (i >= secondLen) msum -= nums[i - secondLen];
            ans = max(ans, lsum + mmax[i + 1]);
            ans = max(ans, msum + lmax[i + 1]);
        }
        return ans;
    }
};

题解 2 - cpp

• 编辑时间：2023-04-26
• 执行用时：12ms
• 内存消耗：8.4MB
• 编程语言：cpp
• 解法介绍：遍历。

vector<int> get_sums(vector<int> &arr) {
    vector<int> sums(1, 0);
    for (auto &num : arr) sums.push_back(sums.back() + num);
    return sums;
}
class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        int n = nums.size(), res = 0;
        auto sums = get_sums(nums);
        for (int i = 0; i + firstLen <= n; i++) {
            int num = sums[i + firstLen] - sums[i];
            for (int j = 0; j + secondLen < i; j++) res = max(res, sums[j + secondLen] - sums[j] + num);
            for (int j = i + firstLen; j + secondLen <= n; j++) res = max(res, sums[j + secondLen] - sums[j] + num);
        }
        return res;
    }
};

题解 3 - python

• 编辑时间：2023-04-26
• 执行用时：260ms
• 内存消耗：15MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
        sums = [0]
        for num in nums:
            sums.append(sums[-1] + num)
        n = len(nums)
        res = i = 0
        while i + firstLen <= n:
            num = sums[i+firstLen] - sums[i]
            j = 0
            while j + secondLen < i:
                res = max(res, sums[j + secondLen] - sums[j] + num)
                j += 1
            j = i + firstLen
            while j + secondLen <= n:
                res = max(res, sums[j + secondLen] - sums[j] + num)
                j += 1
            i += 1
        return res

题解 4 - rust

• 编辑时间：2023-04-26
• 执行用时：4ms
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：同上。

fn get_sums(arr: &Vec<i32>) -> Vec<i32> {
    let mut sums = vec![0];
    for num in arr {
        sums.push(sums.last().unwrap() + *num);
    }
    sums
}
impl Solution {
    pub fn max_sum_two_no_overlap(nums: Vec<i32>, first_len: i32, second_len: i32) -> i32 {
        use std::cmp::max;
        let sums = get_sums(&nums);
        let (first_len, second_len) = (first_len as usize, second_len as usize);
        let n = nums.len();
        let mut res = 0;
        let mut i = 0;
        while i + first_len <= n {
            let num = sums[i + first_len] - sums[i];
            let mut j = 0;
            while j + second_len < i {
                res = max(res, sums[j + second_len] - sums[j] + num);
                j += 1;
            }
            j = i + first_len;
            while j + second_len <= n {
                res = max(res, sums[j + second_len] - sums[j] + num);
                j += 1;
            }
            i += 1
        }
        res
    }
}