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

Categories:

题目描述
思路分析
1. 解法一：前缀和 + 枚举顺序（推荐）
相似题目

题目描述

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

思路分析

解法一：前缀和 + 枚举顺序（推荐）

核心思路：

用前缀和快速计算任意区间和。

分别计算「L 在前、M 在后」与「M 在前、L 在后」两种顺序。

维护当前位置之前的最大 L 子数组和，再拼接当前位置的 M 子数组和。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，用于前缀和。

class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        return Math.max(
                maxSum(nums, firstLen, secondLen),
                maxSum(nums, secondLen, firstLen)
        );
    }

    private int maxSum(int[] nums, int L, int M) {
        int n = nums.length;
        int[] pre = new int[n + 1];
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] + nums[i];
        }

        int maxL = pre[L] - pre[0];
        int ans = 0;

        for (int i = L + M; i <= n; i++) {
            // 更新前缀中 L 子数组的最大和
            int lSum = pre[i - M] - pre[i - M - L];
            if (lSum > maxL) {
                maxL = lSum;
            }

            // 当前 M 子数组和
            int mSum = pre[i] - pre[i - M];
            ans = Math.max(ans, maxL + mSum);
        }

        return ans;
    }
}

func maxSumTwoNoOverlap(nums []int, firstLen int, secondLen int) int {
	a := maxSumOrder(nums, firstLen, secondLen)
	b := maxSumOrder(nums, secondLen, firstLen)
	if a > b {
		return a
	}
	return b
}

func maxSumOrder(nums []int, L int, M int) int {
	n := len(nums)
	pre := make([]int, n+1)
	for i := 0; i < n; i++ {
		pre[i+1] = pre[i] + nums[i]
	}

	maxL := pre[L] - pre[0]
	ans := 0

	for i := L + M; i <= n; i++ {
		// 更新前缀中 L 子数组的最大和
		lSum := pre[i-M] - pre[i-M-L]
		if lSum > maxL {
			maxL = lSum
		}

		// 当前 M 子数组和
		mSum := pre[i] - pre[i-M]
		if maxL+mSum > ans {
			ans = maxL + mSum
		}
	}

	return ans
}

相似题目

题目	难度	考察点
1031. 两个无重叠子数组的最大和	中等	前缀和
689. 三个无重叠子数组的最大和	困难	前缀和、DP
53. 最大子数组和	中等	动态规划
209. 长度最小的子数组	中等	滑动窗口
560. 和为 K 的子数组	中等	前缀和、哈希
713. 乘积小于 K 的子数组	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/75775771