LeetCode 1031中等动态规划
两个无重叠子数组的最大和 图解题解
这道题到底在问什么
给整数数组 nums 与两个长度 firstLen、secondLen，找两段不重叠的连续子数组(长度分别为这两个值)，返回它们元素和的最大值。长度 firstLen 的那段，既可以在另一段之前、也可以在之后。
- 输入
- nums=[6,7,1,9,2,3,1], firstLen=1, secondLen=2
- 输出
- 22
最优解：一步一步想明白
- 3把整套思路压成两句:前缀和让窗口和「一减就得」；扫的时候一个窗口固定、另一个取左侧历史最优 t。两种前后顺序都要扫一趟。下面每帧都在套它。
- 4先建前缀和 s，从一个哨兵 s0 = 0 开始，它代表「前 0 个数的和」。有了这个起点，后面每个 s 都能在上一个的基础上加一个数得到。
- 5把第 0 个数 6 累进来:s1 等于上一项 s0 的 0 再加 6，得 6。前缀和就是这样一路滚出来的。
- 6把第 1 个数 7 累进来:s2 等于上一项 s1 的 6 再加 7，得 13。前缀和就是这样一路滚出来的。
- 7把第 2 个数 1 累进来:s3 等于上一项 s2 的 13 再加 1，得 14。前缀和就是这样一路滚出来的。
- 8把第 3 个数 9 累进来:s4 等于上一项 s3 的 14 再加 9，得 23。前缀和就是这样一路滚出来的。
- 9把第 4 个数 2 累进来:s5 等于上一项 s4 的 23 再加 2，得 25。前缀和就是这样一路滚出来的。
- 10把第 5 个数 3 累进来:s6 等于上一项 s5 的 25 再加 3，得 28。前缀和就是这样一路滚出来的。
- 11把第 6 个数 1 累进来:s7 等于上一项 s6 的 28 再加 1，得 29。前缀和就是这样一路滚出来的。
- 12验证一下这个减法:框住第 0 到第 1 格这段，它的和就是 s2 减 s0，等于 13 减 0，正好 13，也就是 6 加 7。以后任何定长窗口和都这么一减得到，O(1)。
- 13先扫第一趟，约定:长度 1 的窗口落在长度 2 的窗口「前面」。我们让第二个窗口从左往右扫，第一个窗口就在它左边取历史最优，用滚动变量 t 记着。t 和这一趟的答案 ansA 都从 0 起。
- 14第二窗滑到 [1,2]，这两个数的和是 8。它左边能放的最好第一窗(绿色)和是 t = 6，两段相加 14。比之前更大，ansA 刷新成 14。（这一步顺手把第一窗最优 t 更新到了 6。）
- 15第二窗滑到 [2,3]，这两个数的和是 10。它左边能放的最好第一窗(绿色)和是 t = 7，两段相加 17。比之前更大，ansA 刷新成 17。（这一步顺手把第一窗最优 t 更新到了 7。）
- 16第二窗滑到 [3,4]，这两个数的和是 11。它左边能放的最好第一窗(绿色)和是 t = 7，两段相加 18。比之前更大，ansA 刷新成 18。
- 17第二窗滑到 [4,5]，这两个数的和是 5。它左边能放的最好第一窗(绿色)和是 t = 9，两段相加 14。没超过当前 ansA = 18，先记着继续。（这一步顺手把第一窗最优 t 更新到了 9。）
- 18第二窗滑到 [5,6]，这两个数的和是 4。它左边能放的最好第一窗(绿色)和是 t = 9，两段相加 13。没超过当前 ansA = 18，先记着继续。
- 19再扫第二趟，把顺序反过来:这回长度 2 的窗口落在「前面」，长度 1 的窗口在它右边扫。角色对调:t 现在记「左边最好的长度 2 窗口和」，t 和 ansB 重新从 0 起。
- 20第一窗滑到 [2,2]，和是 1。它左边最好的长度 2 窗口(绿色)和是 t = 13，两段相加 14。刷新 ansB 到 14。（这一步把第二窗最优 t 更新到了 13。）
- 21第一窗滑到 [3,3]，和是 9。它左边最好的长度 2 窗口(绿色)和是 t = 13，两段相加 22。刷新 ansB 到 22。
- 22第一窗滑到 [4,4]，和是 2。它左边最好的长度 2 窗口(绿色)和是 t = 13，两段相加 15。没超过 ansB = 22。
- 23第一窗滑到 [5,5]，和是 3。它左边最好的长度 2 窗口(绿色)和是 t = 13，两段相加 16。没超过 ansB = 22。
- 24第一窗滑到 [6,6]，和是 1。它左边最好的长度 2 窗口(绿色)和是 t = 13，两段相加 14。没超过 ansB = 22。
- 25回放最优解:绿色是长度 2 的窗口 [6,7]，和 13，落在左边；右边方框是长度 1 的窗口 [9]，和 9。两段相加 22。注意它来自第二趟，长度 2 的窗口反而在前。这正是为什么两种顺序都得扫:只扫第一趟只会拿到 18。
⚠️ 容易写错的地方
✗ 错：只扫一种顺序
✓ 对：正反两趟都扫，最后取 max
两段谁前谁后都合法，漏一种就可能错过最优(本例只扫第一趟只得 18)
✗ 错：窗口和每次重新累加
✓ 对：前缀和两端相减 O(1) 取窗口和
重复累加会退化成 O(n²)，前缀和把它压回 O(n)
✗ 错：前缀和下标错位
✓ 对：窗口 [l,r] 的和 = s[r+1] − s[l]
写成 s[r] − s[l] 会少算右端那个数
✗ 错：两趟之间忘了重置 t
✓ 对：每趟开头 t 归 0
上一趟的最优窗口和留着，会污染这一趟的判断
完整代码（Python / C++ / Java）
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 ansC++
#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;
}
}复杂度
时间
O(n)
建前缀和一遍 + 两趟各扫一遍，都是线性
空间
O(n)
前缀和数组 s 占 n+1 个位置；滚动变量 t、ans 是常数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 两个无重叠子数组的最大和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么固定一个窗口、另一个取「左边历史最优」就够了，不会漏解？+
因为两段不重叠，这一趟又规定了谁前谁后。当后面那个窗口的位置确定，前面那段必须整段落在它左边，那就在左边所有合法位置里取和最大的一个，和后窗口位置无关。于是一边右移、一边用 t 滚动记住左侧最优，O(n) 就枚举完了所有组合。
不用前缀和可以吗？+
可以。用两个增量滑动窗口和也能做，进一个数加上、出一个数减掉，思路一样。前缀和的好处是把「任意定长窗口和」直接变成两端相减，写起来更直观、更不易错。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 两个无重叠子数组的最大和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。