LeetCode 1031题解析：不重叠子数组最大和的解法（前缀和+动态规划）
一、题目解读
LeetCode 1031题要求在不重叠的前提下，从给定数组nums中寻找两个长度分别为firSTLen和secondLen的连续子数组，使其和最大。题目强调子数组必须不重叠，即两个子数组的区间不能有交集，需要找到最优解。这一问题的关键在于高效计算所有可能的子数组组合并比较其和。
二、解题思路
采用前缀和+动态规划的解题思路。核心思想是利用前缀和数组简化子数组和的计算，再通过动态规划维护四个方向的最大子数组和，从而避免重复遍历。具体策略如下：
1. 计算前缀和数组prefixSum，方便O(1)时间获取任意区间和。
2. 定义四个方向的最大值数组：
○ firstMax：从左到右，长度为firstLen的子数组最大和；
○ secondMax：从左到右，长度为secondLen的子数组最大和；
○ firstMaxFromRight：从右到左，长度为firstLen的子数组最大和；
○ secondMaxFromRight：从右到左，长度为secondLen的子数组最大和。
3. 分别通过正向和逆向遍历计算上述四个数组，确保覆盖所有不重叠组合的可能情况。
4. 遍历所有合法位置，计算两个子数组和的组合最大值，并更新结果。
三、解题步骤
1. 计算前缀和：构建prefixSum数组，其中prefixSum[i+1]表示nums[0]到nums[i]的元素和。
2. 初始化动态规划数组：创建四个辅助数组，用于记录不同方向的最大子数组和。
3. 正向计算：从左到右遍历，更新firstMax和secondMax，利用当前子数组和与历史最大值比较更新结果。
4. 逆向计算：从右到左遍历，更新firstMaxFromRight和secondMaxFromRight，同样采用动态规划思路。
5. 遍历组合：通过两个指针分别指向两个子数组的起始位置，计算所有合法组合的和，取最大值作为最终结果。
四、代码及注释
class Solution {
public:
int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
int n = nums.size();
vector<int> prefixSum(n + 1, 0);
// 计算前缀和数组
for (int i = 0; i < n; ++i) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
// 初始化四个数组用于记录不同情况下的最大值
vector<int> firstMax(n, 0); // 记录到i位置为止firstLen长度的子数组最大值
vector<int> secondMax(n, 0); // 记录到i位置为止secondLen长度的子数组最大值
vector<int> firstMaxFromRight(n, 0); // 记录从i位置开始往右firstLen长度的子数组最大值
vector<int> secondMaxFromRight(n, 0); // 记录从i位置开始往右secondLen长度的子数组最大值
// 从左到右计算firstMax和secondMax
for (int i = firstLen - 1; i < n; ++i) {
int currentSum = prefixSum[i + 1] - prefixSum[i + 1 - firstLen];
if (i == firstLen - 1) {
firstMax[i] = currentSum;
} else {
firstMax[i] = max(firstMax[i - 1], currentSum);
}
}
for (int i = secondLen - 1; i < n; ++i) {
int currentSum = prefixSum[i + 1] - prefixSum[i + 1 - secondLen];
if (i == secondLen - 1) {
secondMax[i] = currentSum;
} else {
secondMax[i] = max(secondMax[i - 1], currentSum);
}
}
// 从右到左计算firstMaxFromRight和secondMaxFromRight
for (int i = n - firstLen; i >= 0; --i) {
int currentSum = prefixSum[i + firstLen] - prefixSum[i];
if (i == n - firstLen) {
firstMaxFromRight[i] = currentSum;
} else {
firstMaxFromRight[i] = max(firstMaxFromRight[i + 1], currentSum);
}
}
for (int i = n - secondLen; i >= 0; --i) {
int currentSum = prefixSum[i + secondLen] - prefixSum[i];
if (i == n - secondLen) {
secondMaxFromRight[i] = currentSum;
} else {
secondMaxFromRight[i] = max(secondMaxFromRight[i + 1], currentSum);
}
}
int result = 0;
// 情况1：firstLen子数组在secondLen子数组左边
for (int i = firstLen - 1; i < n - secondLen; ++i) {
result = max(result, firstMax[i] + secondMaxFromRight[i + 1]);
}
// 情况2：secondLen子数组在firstLen子数组左边
for (int i = secondLen - 1; i < n - firstLen; ++i) {
result = max(result, secondMax[i] + firstMaxFromRight[i + 1]);
}
return result;
}
};五、总结
本解法通过前缀和数组大幅降低子数组和的计算复杂度，结合动态规划的思想维护不同方向的最大值，最终通过遍历所有合法组合找到最优解。时间复杂度O(n)，空间复杂度O(n)，高效解决了不重叠子数组求和问题。关键点在于利用前缀和的预处理与动态规划的双向计算，避免了暴力枚举的指数级时间消耗，是解决此类问题的经典思路。
原创内容 转载请注明出处
