两个无重叠子数组的最大和 图解题解

两个无重叠子数组的最大和在挑什么

给一个整数数组 nums 和两个长度 firstLen、secondLen，要找两段连续、互不重叠的子数组（子数组就是数组里挨着的一截），长度分别是这两个值，让两段元素和最大。题面 nums=[6,7,1,9,2,3,1]、firstLen=1、secondLen=2，答案 22。长度 firstLen 的段既能在另一段左边，也能在右边。

为什么逐对枚举两段位置会慢到跑不动

两段各自的起点都有大约 n 个，两两配对再查重叠就是 n² 量级，每对还要现算两段和，整体奔着 O(n³)（大 O 记号描述规模变大时操作数怎么涨）去，n 一大就跑不动。慢在重复：同一段的和被反复从头累加，同一种前后配置被换着枚举多遍。

前缀和凭什么让定长窗口和一减就得

最好省的是「反复算一段的和」。先建前缀和数组 s（前缀和就是从头累加到每个位置的总和）：s[0]=0 当哨兵、代表前 0 个数的和，s[k] 就是前 k 个数的总和。有了它，第 l 到 r 这段和就是 s[r+1]-s[l]，一次减法 O(1) 拿到。框住第 0 到第 1 格，和是 s[2]-s[0]=13-0=13，正好是 6 加 7。

一段固定另一段取左侧最优，两种顺序为何都要扫

配对不漏。先钉死一种顺序：长度 firstLen 的段在 secondLen 段左边。从左往右滑右段，滑到每处，左边可放的 firstLen 段里只有和最大的才可能最优——用滚动变量 t（一路扫、只记左侧至今最大的段和）盯住。右段每滑一步，先把新空出、能当左段的位置并入 t 取最大，再用 t 加当前右段和刷新答案，一趟就覆盖了「firstLen 段在前」的所有配对。

但 firstLen 段也可能在后。角色对调再扫第二趟：secondLen 段在左、t 改记左侧最优的 secondLen 段和，firstLen 段在右滑。两趟共用 ans 取最大，两种顺序就都兜住。

拿题面数组把两趟扫描亲手走一遍

先滚出 s=[0,6,13,14,23,25,28,29]。第一趟 firstLen=1 段在前、secondLen=2 段右滑：[7,1] 和 8、t=6 合 14；[1,9] 和 10、t=7 合 17；[9,2] 和 11、t=7 合 18；[2,3] 时 t 升到 9 但只合 14；[3,1] 合 13——第一趟最好 18。第二趟对调：右段到 [9] 时左侧最优的长度 2 段是 [6,7]、t=13 合 22，其余都不过 22。取大得 22，来自第二趟——长度 2 段 [6,7] 反在前。

只扫一趟为什么会把答案 22 算成 18

只扫第一趟就返回会把答案定在 18：那趟默认长度 1 的段永远在前，可最优解偏是长度 2 的 [6,7] 在前、长度 1 的 [9] 在后，得第二趟才扫到。复杂度上，前缀和一遍、两趟各扫一遍都是线性，时间 O(n)；额外空间主要是那条长度 n+1 的前缀和数组，空间 O(n)。两个边界：每趟开头必须把 t 清零，否则第二趟会把上一趟的旧最优错当本趟左段；两段长度之和等于数组长度时，答案就是整个数组的和。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
        n = len(nums)
        s = list(accumulate(nums, initial=0))
        ans = t = 0
        i = firstLen
        while i + secondLen - 1 < n:
            t = max(t, s[i] - s[i - firstLen])
            ans = max(ans, t + s[i + secondLen] - s[i])
            i += 1
        t = 0
        i = secondLen
        while i + firstLen - 1 < n:
            t = max(t, s[i] - s[i - secondLen])
            ans = max(ans, t + s[i + firstLen] - s[i])
            i += 1
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        int n = nums.size();
        vector<int> s(n + 1);
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + nums[i];
        }
        int ans = 0;
        for (int i = firstLen, t = 0; i + secondLen - 1 < n; ++i) {
            t = max(t, s[i] - s[i - firstLen]);
            ans = max(ans, t + s[i + secondLen] - s[i]);
        }
        for (int i = secondLen, t = 0; i + firstLen - 1 < n; ++i) {
            t = max(t, s[i] - s[i - secondLen]);
            ans = max(ans, t + s[i + firstLen] - s[i]);
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int n = nums.length;
        int[] s = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + nums[i];
        }
        int ans = 0;
        for (int i = firstLen, t = 0; i + secondLen - 1 < n; ++i) {
            t = Math.max(t, s[i] - s[i - firstLen]);
            ans = Math.max(ans, t + s[i + secondLen] - s[i]);
        }
        for (int i = secondLen, t = 0; i + firstLen - 1 < n; ++i) {
            t = Math.max(t, s[i] - s[i - secondLen]);
            ans = Math.max(ans, t + s[i + firstLen] - s[i]);
        }
        return ans;
    }
}