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

2022-05-08 HGNULB 约 4 分钟

文章信息 6 个分类 · 3 个标签

分类

LeetCode CodeTop 中等 未解决 5-10 字节

标签

数组 动态规划 滑动窗口

题目描述

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

题意分析

选择两段固定长度的连续子数组，要求互不重叠，使总和最大。两种长度的区间可以位于任意一侧，中间允许有空隙。

解法：前缀和 + 前缀最优

核心思路

[!blue]

两个不重叠的区间一定有左右顺序。先固定左段长度为 leftLen、右段长度为 rightLen，求这种顺序下的最大和；再交换两种长度扫描一次，取较大结果，就覆盖了所有合法组合。

定义 prefix[i] 为 nums[0, i) 的和，区间 [l, r) 的和就是 prefix[r]-prefix[l]。枚举右段起点 rightStart 时，右段 [rightStart, rightStart+rightLen) 已确定，只需从它左边所有长度为 leftLen 的区间中选择最大和。

用 bestLeft 保存这些合法左段的最大和。rightStart 每右移一格，之前的左段仍然合法，唯一新增的候选是刚好在右段前结束的 [rightStart-leftLen, rightStart)。先把它的和并入 bestLeft，再加上当前右段和，就得到以当前右段为固定选择时的最优答案。保留历史最大值也自然允许两段之间有空隙。

rightStart 从 leftLen 开始，直到 rightStart+rightLen > n 才停止，保证左右两段都有足够长度。题目保证两种长度之和不超过 n，所以至少存在一种组合；元素均非负，因此 bestLeft 和 answer 可以从 0 开始。

解题步骤

1. 构造长度为 n+1 的前缀和数组，令 prefix[0] = 0。
2. 固定左右长度，枚举 rightStart 从 leftLen 到 n-rightLen。
3. 用 prefix[rightStart]-prefix[rightStart-leftLen] 更新 bestLeft，纳入刚刚变得合法的左段。
4. 计算当前右段和，以 bestLeft+rightSum 更新 answer。
5. 交换 firstLen 和 secondLen 再扫描一次，返回两种顺序的较大值。

代码实现

class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int[] prefix = new int[nums.length + 1];

        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        return Math.max(
                maxWithOrder(prefix, firstLen, secondLen),
                maxWithOrder(prefix, secondLen, firstLen));
    }

    // 本次固定两种长度的左右顺序，交换参数再覆盖另一种顺序
    private int maxWithOrder(int[] prefix, int leftLen, int rightLen) {
        int n = prefix.length - 1;
        int bestLeft = 0;
        int answer = 0;

        for (int rightStart = leftLen; rightStart + rightLen <= n; rightStart++) {
            // 先纳入刚好在右区间之前结束的左段
            int leftSum = prefix[rightStart] - prefix[rightStart - leftLen];

            bestLeft = Math.max(bestLeft, leftSum);

            // 历史最优左段允许与当前右段之间留有空隙
            int rightSum = prefix[rightStart + rightLen] - prefix[rightStart];

            answer = Math.max(answer, bestLeft + rightSum);
        }

        return answer;
    }
}

func maxSumTwoNoOverlap(nums []int, firstLen int, secondLen int) int {
    prefix := make([]int, len(nums)+1)
    for i, num := range nums {
        prefix[i+1] = prefix[i] + num
    }

    firstBeforeSecond := maxWithOrder(prefix, firstLen, secondLen)
    secondBeforeFirst := maxWithOrder(prefix, secondLen, firstLen)
    if firstBeforeSecond > secondBeforeFirst {
        return firstBeforeSecond
    }
    return secondBeforeFirst
}

// 本次固定两种长度的左右顺序，交换参数再覆盖另一种顺序
func maxWithOrder(prefix []int, leftLen int, rightLen int) int {
    n := len(prefix) - 1
    bestLeft, answer := 0, 0

    for rightStart := leftLen; rightStart+rightLen <= n; rightStart++ {
        // 先纳入刚好在右区间之前结束的左段
        leftSum := prefix[rightStart] - prefix[rightStart-leftLen]
        if leftSum > bestLeft {
            bestLeft = leftSum
        }

        // 历史最优左段允许与当前右段之间留有空隙
        rightSum := prefix[rightStart+rightLen] - prefix[rightStart]
        if bestLeft+rightSum > answer {
            answer = bestLeft + rightSum
        }
    }
    return answer
}

复杂度分析

• 时间复杂度：$O(n)$，n 为数组长度，构造前缀和并执行两次线性扫描。
• 空间复杂度：$O(n)$，保存前缀和。

关键点总结

[!green]

• 历史最优必须覆盖所有此前合法左段，不只是紧挨右段的一段。
• 先更新左段候选，才能包含恰好相邻的组合。

易错点总结

[!yellow]

• 只计算一种长度顺序会漏解。
• 将右段中的元素算入左段，产生重叠。
• 右段终点不允许等于数组长度，会漏掉末尾组合。

相似题目

题目	难度	关联与区别
689. 三个无重叠子数组的最大和	困难	同样组合互不重叠的固定长度窗口，原题要选三段，本题只选两段但长度可不同。
1235. 规划兼职工作	困难	通用不重叠区间收益可用DP，本题固定两段长度，可用前缀或后缀最优值简化。

转载与许可

作者 HGNULB

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

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！